Diskussion:PSPACE

Polynomiell in was?

Es sollte geschrieben (und referenziert) werden, in was der Platzbedarf polynomiell ist. Ich glaube er ist polynomiell abhängig von der Zeit (jedenfalls wurde das gerade so in einer Vorlesung gesagt - macht für mich gerade allerdings wenig sinn, da mir nicht klar ist wie man z.B. quadratisch viel Platz in abhängigkeit von der Zeit bei einer standard-Turingmaschine nutzen kann). --Martin Thoma 09:25, 17. Jun. 2015 (CEST)

Bei der Klasse PSPACE ist der verwendete Speicher polynomiell in der Größe der Eingabe. Das wird in der Definition von Platzkomplexität so festgelegt - es schadet aber sicher nicht das hier nochmal zu betonen. Insbesondere darf in PSPACE die Zeit exponentiell in der Größe der Eingabe sein (das macht den Unterschied zu Ptime aus wo Beides, Speicher und Zeit, polynomiell in der Größe der Eingabe sind). -- Wdvorak (Diskussion) 11:18, 17. Jun. 2015 (CEST)

Ok, so kenne ich das auch. Aber das widerspricht ganz direkt dem, was ein Dozent heute in einer Vorlesung gesagt hat. Es wäre schön, wenn man die Definition direkt zitieren könnte. Ich habe gerade mal in meinen Büchern geschaut, aber dort wird PSPACE immer nur in Nebensätzen à la "Das Problem ist in NPC (sogar PSPACE-vollständig)" erwähnt. --Martin Thoma 20:19, 17. Jun. 2015 (CEST)

Du hast Recht ein Abschnitt mit einer "formalen" Definition wäre gut. Für die PSPACE Definition muss man in dezidierte Komplexitätstheorie Bücher schauen (z.B.: [1] (Entwurfsversion frei verfügbar)). Theoretische Informatik Bücher stossen da an Ihre Grenzen. BTW: NPC passt mit PSPACE-vollständig (nach den vermuteten Relationen zwischen Komplexitätsklassen) nicht zusammen. Die Intuition von PSPACE-vollständig ist dass es in NP nicht lösbar ist --Wdvorak (Diskussion) 10:36, 18. Jun. 2015 (CEST)

NP-schwer vs NP-vollständig

Im Artikel steht, dass "Die Inklusion NP $\subseteq$ PSPACE ergibt sich daraus, dass lediglich für ein beliebiges NP-schweres Problem gezeigt werden muss, dass es in PSPACE liegt." Der Argumentation kann ich so nicht folgen, da NP-schwere Probleme nicht in NP liegen müssen. Übersehe ich vielleicht was? Danke Isomorphismus (Diskussion) 23:34, 17. Nov. 2020 (CET)

NP-schwere Probleme sind ja mindestens so schwer wie NP, dh wenn wir ein NP schweres Problem P haben dann können wir jedes Problem A in NP auf P reduzieren (in Polynomialzeit). Können wir jetzt P in PSPACE lösen dann können wir "PSPACE-Algorithmus" für P mit der Reduktion von A auf P kombinieren und bekommen einen "PSPACE-Algorithmus" für A. Die Argumentation im Artikel sollte daher aus meiner Sicht so passen. Wenn man aber ein NP-schweres Problem wählt das nicht in PSPACE liegt wird der Beweis natürlich nicht gelingen. -- Wdvorak (Diskussion) 10:06, 19. Nov. 2020 (CET)