Gramatyka kontekstowa dla SAT?

16

Według klasycznego wyniku Kurody, klasa złożoności NSPACE [ ]n (znana również jako NLIN-SPACE) jest właśnie klasą CSL języków kontekstowych . Problem satysfakcji SAT występuje w NSPACE [ ], ponieważ domysły o liniowym rozmiarze dla rozwiązania można sprawdzić z co najwyżej liniowym obciążeniem dla księgowości. Oznacza to, że SAT musi mieć gramatykę kontekstową (CSG).n

Czy ktoś próbował dostarczyć CSG dla SAT?

Zdaję sobie sprawę, że wiele pytań związanych z CSL jest nierozstrzygalnych (na przykład decydowanie, czy dany CSG generuje pusty język). Nawet biorąc pod uwagę CSG dla SAT, nadal trzeba by pokonać przeszkodę, że decydowanie o członkostwie w języku podanym przez CSG jest w zasadzie kompletne z PSPACE. Ale może się zdarzyć, że problem członkostwa w CSG, który definiuje SAT, występuje w NP, z powodu jakiejś specjalnej struktury języka. Przeredagowanie, aby odpowiedzieć na komentarz MCH: Ale może się zdarzyć, że problem członkostwa w CSG, który definiuje SAT, może być pokazany w NP ze względu na jakąś specjalną strukturę gramatyki, a nie dlatego, że już wiemy, że musi być NP.


Wyjaśnienie:

Zamierzonym celem jest tutaj specjalna funkcja gramatyki dla SAT, która pozwala na rozpoznanie jej przez maszynę NTIME [poli ( )], a nie przez NSPACE [ ] DTIME [ ] uwiązany.nn2)O(n)

Dowód twierdzenia 3 w pracy Landwebera z 1963 r. Konstruuje CSG z automatu ograniczonego liniowo. (Kuroda podał odwrotnie, konstruując automat związany z liniami dla dowolnego CSG.) Jednak procedura Landwebera nie wydaje się dostarczać gramatyki dla SAT, która ma specjalną formę: wszystkie urządzenia rozpoznające NSPACE [ ] są traktowane w ten sam ogólny sposób. Innymi słowy, nie jest jasne, dlaczego SAT CSG powinien mieć problem z członkostwem NP, a nie być ukończony PSPACE. Miałem nadzieję na bardziej jednoznaczną konstrukcję, która wykorzystywałaby NP-SAT w jakiś istotny sposób.n

Być może lepszym, bardziej precyzyjnym pytaniem jest, czy:

  1. istnieje automat z ograniczeniem liniowym, który rozpoznaje SAT,
  2. z którego można wydobyć CSG,
  3. więc język zdefiniowany przez CSG jest w NP z powodu jakiejś cechy gramatyki (a nie dlatego, że już wiemy, że jest w NP)?

W ciągu pięciu dekad z pewnością ktoś próbował to zrobić! Ponieważ nie mogę znaleźć niczego opublikowanego w ten sposób, chciałbym zrozumieć, dlaczego to podejście nie zadziałało, lub wskaźnik do pracy, za którym tęskniłem.

András Salamon
źródło
5
Nie rozumiem. Czy nie możesz po prostu wykonać dowodu i wyprodukować CSG dla SAT? Czy to nie jest konstruktywne? Również w ostatnim zdaniu: „może być tak, że problem członkostwa w CSG, który definiuje SAT, występuje w NP”, dotyczy NP, ponieważ problemem członkostwa jest tylko SAT, czyli NP.
MCH
1
@MCH: Dziękuję za komentarz, mam nadzieję, że edycja wyjaśni pytanie.
András Salamon
brzmi to jak inny sposób na sformułowanie tego, może wyglądać tak: istnieją CSL / CSG, które są rozpoznawalne w czasie NP w (w przeciwieństwie do PSPACE w ogólnym przypadku) na podstawie konwersji SAT. co jest specjalnego w ich „strukturze”, która na to pozwala? konwersja SAT do CSL / CSG może dać „podpowiedź”, ale nie jest to konieczne. podać bardziej ogólne kryteria. innymi słowy, biorąc pod uwagę arbitralny CSL / CSG, czy istnieją jakieś kryteria wskazujące, że jego rozpoznanie jest faktycznie w NP?
vzn

Odpowiedzi:

9

Choć nie konstruuje bezpośrednio gramatyki kontekstowej dla SAT, poniższy artykuł może rzucić nieco światła.

Rundy WC, złożoność rozpoznawania w językach pośrednich , teoria przełączania i automatu, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5

Artykuł Roundsa podaje jednokierunkowy niedeterministyczny automat stosu (1-NSA) rozpoznający SAT, a następnie pokazuje problem członkostwa w 1-NSA (i jego odpowiednim nadzbirze, Indeksowana gramatyka Aho) jest ogólnie w NP. Innymi słowy, SAT jako automat CSL / liniowy jest wyjątkowy, ponieważ wykorzystuje swoją pamięć tylko jako stos.

kinaba
źródło
4
Dzięki, dokładnie tego szukałem! Rounds pokazuje, że SAT jest językiem stosu jednokierunkowego, językiem indeksowanym i językiem przetwornika drzewa, co daje trzy różne teoretyczne powody, dla których jest on wyjątkowy.
András Salamon,
więc może „wystarczające”, ale nie jest od razu jasne, czy warunki te są konieczne (aby rozpoznanie CSL / CSG było w NP). więc wydaje mi się, że twoje ogólne pytanie może nie być zbytnio badane. CSL / CSG wydają się nie mieć za sobą wielu badań.
dniu
dalej się nad tym zastanowić. jego problemem jest ogólnie postać „rozpoznawania języka w większej klasie Y, w rzeczywistości w mniejszej klasie językowej X”. dla Y = CFG i X = RLs (zwykły język) problem jest nierozstrzygalny, patrz np. czy to cfg definiuje zwykły język . dlatego też Y = CSL i X = NP wydają się być w ogóle nierozstrzygalne.
vzn