Języki kompletne i wrażliwe na kontekst.

Interesują mnie dwa pytania dotyczące języków kontekstowych (CSL) i kompletności:

Czy istnieje pojęcie kompletności CSL i które języki są kompletne?
Czy istnieją naturalne CSL, które są NP-kompletne?

W przypadku 2. z pewnością mogę myśleć o naturalnych językach NP-zupełnych, które są CSL (ponieważ CSL jest równy NSPACE [ $n$ ], SAT to CSL), ale szukam , tj. Kontekstu wrażliwa gramatyka opisująca język NP-zupełny.

np-hardness fl.formal-languages space-bounded Michaël Cadilhac
źródło

Zobaczmy, czy rozumiem poprawnie (2): Czy wystarczy napisać gramatykę kontekstową, która generuje wszystkie prawidłowe instancje 3SAT na stałym alfabecie łączników i zmiennych SAT?

Evgenij Thorstensen

Cóż, nie dodałbym zmiennych SAT jako części alfabetu (kodowanie binarne ich indeksów jest wystarczająco dobre), ale to z pewnością odpowiedziałoby na mój drugi punkt!

Michaël Cadilhac

Nawiasem mówiąc, próbowałeś?

Michaël Cadilhac

(1) Jak wspomniałeś, możliwe jest zapisanie CSG dla 3SAT, ale to brzmi podobnie do spisania pełnego opisu maszyny Turinga dla problemu maksymalnego przepływu (lub dowolnego konkretnego języka w P); Nie spodziewałbym się, że da to jakiś wgląd w teorię złożoności. (Ale hej, jeśli okaże się inaczej, z przyjemnością to usłyszę.) (2) Zasadniczo pojęcie gramatyki kontekstowej i pojęcie kompletności NP nie pasują do siebie, ponieważ zestaw kontekstowy języki nie są zamknięte w ramach redukcji czasu wielomianowego.

Tsuyoshi Ito,

Dzięki za komentarz Tsuyoshi. Rzeczywiście, gramatyka dla 3SAT prawdopodobnie nie jest tym, czego szukam, ale poszedłem z taką samą reakcją jak twoja: jeśli jest to nieco łatwe / naturalne, byłbym zainteresowany. Dla twojego (2) jednym z moich celów jest: powiedz, że mam klasę języków CS zamkniętych przez redukcję przestrzeni logicznej i chcę pokazać, że moja klasa nie zawiera (lub jest mało prawdopodobne) problemów z NP Musiałbym tylko wykazać, że określony język NP-zupełny CS nie znajduje się w mojej klasie, co może być łatwiejsze, jeśli językiem jest oczywiście CS.

Michaël Cadilhac 10.10.10

Odpowiedzi:

Aby odpowiedzieć na twoje pierwsze pytanie, redukcją odpowiadającą twoim potrzebom jest redukcja log-lin-redukcja, która jest redukcją przestrzeni logarytmicznej z dodatkowym ograniczeniem, że rozmiar ciągu wyjściowego redukcji jest co najwyżej liniowy w stosunku do wielkości wejściowej. Jeśli dobrze pamiętam, problem członkostwa w gramatyce kontekstowej (lub, jeśli wolisz, liniowo ograniczone automaty), to kanoniczny problem z CSL-em, który redukuje log-lin.

Po stronie zastosowanej problemem uniwersalności (zwykłych) wyrażeń regularnych nad binarnym alfabetem jest pełna CSL wrt log-lin-redukowalność. Pojęcie i wynik kompletności znajdują się w Albert R. Meyer i Larry J. Stockmeyer (SWAT 1972) również: Stockmeyer (praca doktorska, MIT 1974). Aby uzyskać dalsze informacje i podobne wyniki w tym obszarze, zobacz także niedawne badanie przeprowadzone przez Holzer i Kutrib (DLT 2010).

EDYCJA (2017/03/06): Jeśli chodzi o twoje drugie pytanie, w zaakceptowanej odpowiedzi na poniższe pytanie przytacza się artykuł Roundsa (1973), który konstruuje jednokierunkowy automat z zagnieżdżonymi stosami rozpoznający SAT. Chociaż SAT nie kwalifikuje się jako „naturalny” CSL, warto poszukać w literaturze innych przykładów automatów stosu jednokierunkowego lub gramatyki indeksowanej.

Gramatyka kontekstowa dla SAT?

Hermann Gruber
źródło

Dziękuję bardzo, tego właśnie szukałem!

Michaël Cadilhac

Do edycji: Fantastycznie! Dziękujemy za powrót i wypełnienie tej odpowiedzi. To wspaniały duch!

Michaël Cadilhac