Moin,

hat jemand von euch ne Ahnung, wie das um die Komplexität von REC steht? Gut, alles unter Typ-0 ist entscheidbar, sagt aber nichts darüber, ob alle Sprachen in REC auch in polynomieller Zeit von einer TM erkannt werden. Vielleicht hab ich ja was im Skript übersehen … aber nun vermute ich, dass P Teilmenge von REC ist.

Über NP denke ich genauso, über PSpace mag ich gar nicht erst nachdenken. Vielleicht jat ja jemand eine Idee.

Gut, alles unter Typ-0 ist entscheidbar,

Wenn du damit meinst, dass alle Typ-1-Sprachen entscheidbar
sind, ist das richtig (aber nicht alle Typ-0-Sprachen sind
entscheidbar!).

sagt aber nichts darüber, ob alle Sprachen in REC auch in polynomieller Zeit von einer TM erkannt werden. Vielleicht hab ich ja was im Skript übersehen … aber nun vermute ich, dass P Teilmenge von REC ist.

Ja, P ist eine echte Teilmenge von REC. Denn es gibt zu jeder
rekursiven Zeitschranke eine entscheidbare Sprache, die nicht
mit dieser Zeitbeschränkung von einer DTM akzeptiert werden kann
(falls dieser Satz nicht im Skript stehen sollte, kannst du ihn im
Buch von Reischuk nachlesen; die Menge wird mit Diagonalisierung
konstruiert). Insbesondere zur Zeitschranke [img]http://mokrates.de/cgi-bin/texstring?2%5En[/img], also
gibt es eine entscheidbare Sprache, die nicht in polynomieller Zeit
von einer DTM akzeptiert werden kann.

Über NP denke ich genauso,

Ja, da gilt das gleiche. Denn man kann mit obigem Satz eine
entscheidbare Sprache konstruieren, die sich nicht mit der
Zeitbeschränkung [img]http://mokrates.de/cgi-bin/texstring?2%5E%7B2%5En%7D[/img] von einer DTM akzeptieren
lässt (und die ist dann nicht in NP enthalten).

über PSpace mag ich gar nicht erst nachdenken.

Das gilt ebenfalls und mit fast dem gleichen Argument.
Man kann auch zu jeder Platzschranke eine entscheidbare
Sprache konstruieren, die mit dieser von einer DTM nicht
akzeptiert werden kann. Die Konstruktion dieser Sprache geht
genauso wie die bei Reischuk angegebene für Zeitschranken,
man muss sich allerdings noch überlegen, warum die
für die Platzschranke konstruierte Sprache noch
entscheidbar ist.

Erstmal danke für die ausführliche Antwort.

Leider ist mir ein Fehler unterlaufen … ich meine nicht REC sondern REG (entschuldige!) Du hast mir aber trotzdem geholfen, denn dass PSpace auch noch entscheidbar ist, wusste ich nicht. Der Rest der Hierarchie ist ja im Schöning aufgemalt.

Also, ich war soweit, dass ich wusste, dass REG und alles darüber bis inkl. Typ-1 entscheidbar ist. Aber ist es auch in P? Oder gibt es sogar Probleme aus REG, die PSpace vollständig sind? Die beiden Klassen liegen ja auch in REC. Darüber hab ich noch nichts im Skript finden können.

Bei REG ist es doch noch viel einfacher. Diese
Sprachen können ja allein durch die endliche
Kontrolle einer DTM akzeptiert werden. Beim
Akzeptieren braucht diese TM dann nur den Platz
für das Eingabewort, hat also eine lineare
Platzbeschränkung. Außerdem kann die DTM das
Wort ja in linearer Zeit akzeptieren (für jedes
Symbol einen Schritt).

Wenn es nun eine PSPACE-vollständige Sprache in REG
gibt, so wäre sie insbesondere in P enthalten und es
würde folgen, dass jedes Problem in PSPACE in polynomieller
Zeit lösbar ist, also P=PSPACE. Die Umkehrung ist
offensichtlich. Es gibt also genau dann eine PSPACE-
vollständige Sprache in REG, wenn P=PSPACE.

Mensch. Stimmt. Leuchtet absolut ein. Danke!