NP liegt in PSPACE

[mensch mit komplexen]

hallo, aller wahrscheinlichkeit liegt ja NP echt in PSPACE. Heißt das, dass PSPACE-hart Probleme schwerer zu lösen sind als alle die in NP liegen?
Ich finde das etwas seltsam, da NP ja mit exponentiellem Rechenaufwand verbunden ist, PSPACE allerdings nur mit polynomialem Platz. exponentiell ist doch eigtl. stärker als polynomial... bin grade echt etwas verwirrt

[borg]

mensch mit komplexen schrieb:

da NP ja mit exponentiellem Rechenaufwand verbunden ist

wer sagt das denn?
in NP sind alle probleme welche von einer nichtdeterministischen turingmaschine in polynomieller zeit gelöst werden können.

[Christoph]

mensch mit komplexen schrieb:

hallo, aller wahrscheinlichkeit liegt ja NP echt in PSPACE. Heißt das, dass PSPACE-hart Probleme schwerer zu lösen sind als alle die in NP liegen?
Ich finde das etwas seltsam, da NP ja mit exponentiellem Rechenaufwand verbunden ist, PSPACE allerdings nur mit polynomialem Platz. exponentiell ist doch eigtl. stärker als polynomial... bin grade echt etwas verwirrt

Rechenaufwand und Platz sind nicht 1:1 austauschbar. Nimm z.B. das Problem des Handlungsreisenden, der eine möglichst kurze Rundreise durch n gegebene Städte machen möchte. Geht man dieses Problem ganz naiv per Tiefensuche an, erhält man sogar eine überexponentielle Laufzeit von O(n!). Der Algorithmus benötigt aber nur ziemlich wenig Speicher: Die maximale Rekursionstiefe bei n Städten ist gerade n, d.h. der Speicher ist sogar linear durch die Anzahl der Städte begrenzt. Wenn du den Speicher jetzt nicht linear, sondern polynomiell begrenzt, kann es gut sein, dass du noch schwere Probleme angehen kannst.

Das entscheidende ist, dass PSPACE keine Einschränkung der Laufzeit macht.

[mensch mit komplexen]

Ok, danke.
Ist es denn so, dass alle PSPACE-vollständigen Probleme schwerer zu lösen sind, als die, die in NP liegen, bzw. nimmt man das an?

[CStoll]

Man nimmt es an (der Status der Frage, ob NP=PSPACE gilt, dürfte ähnlich liegen wie das P-NP-Problem - siehe auch Wikipedia: PSPACE)

Das Verhältnis zu anderen bekannten Komplexitätsklassen ist wie folgt:
NC ⊆ P ⊆ NP ⊆ PSPACE
Es ist bekannt, dass mindestens eine der obigen Inklusionen echt ist und es wird vermutet, dass alle echt sind.