Kontextsensitive Grammatik für SAT?

Nach einem klassischen Ergebnis von Kuroda ist die Komplexitätsklasse NSPACE [ ]$n$ (auch bekannt als NLIN-SPACE) genau die Klasse CSL von kontextsensitiven Sprachen . Das Erfüllbarkeitsproblem SAT liegt in NSPACE [ ] vor, da eine lineare Schätzung für eine Lösung mit höchstens einem linearen Aufwand für die Buchhaltung überprüft werden kann. Dies bedeutet, dass SAT eine kontextsensitive Grammatik (CSG) haben muss.$n$

Hat jemand versucht, eine CSG für SAT bereitzustellen?

Mir ist klar, dass viele Fragen im Zusammenhang mit CSLs nicht entschieden werden können (zum Beispiel, ob eine gegebene CSG die leere Sprache erzeugt). Selbst bei einer CSG für SAT müsste man noch das Hindernis überwinden, dass die Entscheidung über die Mitgliedschaft in der von einer CSG gegebenen Sprache im Allgemeinen PSPACE-vollständig ist. Es kann jedoch vorkommen, dass das Mitgliedsproblem für die CSG, die SAT definiert, aufgrund einer speziellen Struktur der Sprache in NP liegt. Umformulierung, um den Kommentar von MCH anzusprechen: Es kann jedoch vorkommen, dass das Mitgliedsproblem für die CSG, die SAT definiert, aufgrund einer speziellen Struktur der Grammatik in NP angezeigt wird und nicht, weil wir bereits wissen, dass es in sein muss NP.

• S.-Y. Kuroda, Klassen von Sprachen und linear gebundenen Automaten , Information and Control 7 (2) 207–223, 1964. doi: 10.1016 / S0019-9958 (64) 90120-2

Klärung:

Der beabsichtigte Fokus liegt hier auf der Besonderheit der Grammatik für SAT, die es ermöglicht, dass sie von einem NTIME [poly ( )] - Computer anstelle des NSPACE [ ] DTIME [ ] erkannt wird. gebunden.$n$$n$$\subseteq$$2^{O(n)}$

Der Beweis von Satz 3 in Landwebers Arbeit von 1963 konstruiert eine CSG aus einem linear begrenzten Automaten. (Kuroda lieferte das Gegenteil und konstruierte einen linear begrenzten Automaten für jedes CSG.) Landwebers Verfahren scheint jedoch keine Grammatik für SAT zu liefern, die eine besondere Form hat: Alle NSPACE [ ] -Erkenner werden auf dieselbe generische Weise behandelt. Mit anderen Worten, es ist nicht klar, warum die SAT CSG ein NP-Mitgliedsproblem haben sollte, anstatt PSPACE-vollständig zu sein. Ich hatte auf eine explizitere Konstruktion gehofft, die die NP-Ness von SAT auf eine wesentliche Weise nutzt.$n$

Vielleicht ist eine bessere, genauere Frage, ob:

1. es gibt einen linear begrenzten Automaten, der SAT erkennt,
2. aus dem man eine CSG extrahieren kann,
3. damit die von der CSG definierte Sprache aufgrund einiger Merkmale der Grammatik in NP ist (und nicht, weil wir bereits wissen, dass es in NP ist)?

In den letzten fünf Jahrzehnten hat sicherlich jemand versucht, dies zu tun! Da ich nichts in dieser Richtung veröffentlichtes finden kann, wäre ich daran interessiert zu verstehen, warum dieser Ansatz nicht funktioniert hat, oder einen Hinweis auf eine Arbeit, die ich verpasst habe.

• Peter S. Landweber, Drei Sätze über Phrasenstrukturgrammatiken vom Typ 1 , Information und Kontrolle 6 (2) 131–136, 1963. doi: 10.1016 / S0019-9958 (63) 90169-4

Obwohl das folgende Papier nicht direkt eine kontextsensitive Grammatik für SAT erstellt, könnte es etwas Licht ins Dunkel bringen.

WC-Runden, Komplexität der Erkennung in Sprachen der Mittelstufe , Schalt- und Automatentheorie, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5

Die Arbeit von Rounds gibt einen nicht-deterministischen Einweg-Stapelautomaten (1-NSA) an, der SAT erkennt, und zeigt dann, dass das Mitgliedschaftsproblem von 1-NSA (und seiner richtigen Obermenge, Ahos Indexierte Grammatik) im Allgemeinen in NP ist. Mit anderen Worten, SAT als CSL / linear-bounded-automata ist insofern besonders, als es seinen Speicher nur als Stapel verwendet.