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

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