Wortproblem kontextsensitive Grammatiken

Question

Hallo

Im Buch auf der Seite 139 steht, dass das Wortproblem für Typ-1-Sprachen entscheidbar ist, aber PSPACE-vollständig

In einer nuKIT Umfrage zu Kapitel 4 gibt es die Frage:

"Es gibt kontextsensitive Grammatiken, für die das Wortproblem mindestens folgenden Aufwand hat:"

Und dabei ist die Antwort "polynomieller, nichtlinearer Platz" falsch

Ist das jedoch nicht gerade die Definition von PSPACE?

Comments

Gute Frage! Wenn Sie auf meine Antwort nicht gekommen sind, ist das kein Beinbruch ;-) Ich musste auch erstmal nachdenken. (Bitte posten Sie hier noch den genauen Lösungstext, damit wir wissen, wovon die Rede ist.)

Answer 1

Hmm... Doch. Bzw. fast. "Polynomieller Platz" ist (sinngemäß) die Definition von $PSPACE$. Nichtlinear ist nicht gefordert, und das ist auch genau der Punkt.

Gibt es zu der nuKIT-Frage eine Erklärung? Können Sie die mal hier posten, weil ich nicht mehr auswendig weiß, was wir mit der Frage bezweckt haben.

Der Punkt ist, dass man diese Frage tatsächlich strenggenommen nicht mit Ja beantworten kann, und zwar aus folgendem Grund: So wie noch nicht gezeigt werden konnte, dass nicht $P = NP$ gilt, so ist auch unbekannt (wenn auch unwahrscheinlich), ob $NP=PSPACE$ gilt. Also könnte rein theoretisch auch $$P=NP=PSPACE$$ gelten. Es ist sehr unwahrscheinlich, aber ausgeschlossen ist es nicht. Wäre das der Fall, wären alle Probleme aus $PSPACE$, auch die $PSPACE$-vollständigen, in $P$, und dann gäbe es eben keine Typ-1-Grammatiken mit nichtlinearem Platzverbrauch des Wortproblems.

Ich muss allerdings zugeben, dass das im Kontext unserer Vorlesung eine sehr schwierige Frage wäre, wenn es so gemeint gewesen sein sollte.

Comments

Ok, das macht auf jeden Fall Sinn.
Die Frage war:

Es gibt kontextsensitive Grammatiken, für die das Wortproblem (nach heutigem Kenntnisstand) mindestens folgenden Aufwand hat:

    3 votings - lineare Zeit
    6 votings - polynomielle, nichtlineare Zeit
    6 votings - exponentielle Zeit
    1 votings - überexponentielle Zeit
    1 votings - polynomieller, nichtlinearer Platz
    2 votings - überpolynomieller Platz

The Professor's comment to this question:
Das Wortproblem für Typ-1-Sprachen (die den durch kontextsensitive Grammatiken darstellbaren Sprachen entsprechen) ist NP-schwer, braucht also nach heutiger Kenntnis (wegen P != NP) schlimmstenfalls exponentielle Zeit. Siehe auch Folie 4-6 und Kapitel 5.

---

Okay, dann ist aber die Antwort "falsch" falsch. Denn da steht "nach heutigem Kenntnisstand". Und nach diesem sollte es Typ-1-Grammatiken geben, die mehr als linearen Platz benötigen.

---

Ich muss der Vollständigkeit halber hinzufügen: SOLLTE, ja, aber ganz so trivial ist es nicht, das wirklich zu zeigen. Ich habe gerade nochmal nachgelesen, und es gibt auch $PSPACE$-vollständige Probleme, die nur $O(n)$ Platz oder sogar $O\left(n^{0.1}\right)$ Platz usw. brauchen. Das ist recht unintuitiv, ist aber ganz logisch. Also können wir nicht einfach aus der $PSPACE$-Vollständigkeit folgern, dass wir super-linear sind.