Kontextsensitive Grammatik für SAT?

16

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.


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.nn2Ö(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
András Salamon
quelle
5
Ich verstehe nicht Können Sie nicht einfach dem Beweis folgen und die CSG für SAT erstellen? Ist es nicht konstruktiv? Auch über den letzten Satz : „Es könnte der Fall sein , dass die Mitgliedschaft Problem für die CSG , den SAT ist in NP definiert“, es ist in NP , da die Mitgliedschaft Problem nur SAT ist, die in NP ist.
MCH
1
@MCH: Danke für deinen Kommentar, ich hoffe die Bearbeitung klärt die Frage.
András Salamon
Es klingt nach einer anderen Art, dies zu formulieren: Es gibt CSLs / CSGs, die in NP-Zeit (im Gegensatz zu PSPACE im Allgemeinen) auf der Basis der Konvertierung von SAT erkennbar sind. Was ist das Besondere an ihrer "Struktur", die dies ermöglicht? Das Konvertieren von SAT in eine CSL / CSG kann einen "Hinweis" geben, ist jedoch nicht erforderlich. Geben Sie allgemeinere Kriterien an. Mit anderen Worten: Gibt es bei einer willkürlichen CSL / CSG einige Kriterien, die darauf hinweisen, dass die Anerkennung tatsächlich in NP erfolgt?
vzn

Antworten:

9

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.

Kinaba
quelle
4
Danke, genau das, wonach ich gesucht habe! Rounds zeigt, dass SAT eine One-Way-Stack-Sprache, eine indizierte Sprache und eine Tree-Transducer-Sprache ist, und gibt drei verschiedene sprachtheoretische Gründe an, warum es so besonders ist.
András Salamon
also vielleicht "ausreichend", aber es ist nicht sofort klar, ob diese Bedingungen notwendig sind (damit die CSL / CSG-Anerkennung in NP erfolgt). so scheint es mir, dass Ihre allgemeine Frage nicht viel untersucht werden kann. CSLs / CSGs scheinen nicht viel Forschung zu bieten.
vzn
weiter darüber nachgedacht. Es ist ein allgemeines Problem in der Form "ist das Erkennen einer Sprache in der größeren Klasse Y, tatsächlich in der kleineren Sprachklasse X". für Y = CFG und X = RLs (reguläre Sprache) ist das Problem nicht zu entscheiden, siehe z. B. definiert diese CFG eine reguläre Sprache . daher scheinen Y = CSL und X = NP im Allgemeinen ebenfalls unentscheidbar zu sein.
vzn