Czy czas quasi-wielomianowy w PSPACE?

Przeszukałem to, ale i tak nie znalazłem odpowiedzi.

Huck odpowiedział na to w pełni. Dzięki :)

cc.complexity-theory complexity-classes time-complexity space-complexity Tayfun Pay
źródło

Czy możesz przenieść „komentarz w pytaniu” do rzeczywistego komentarza.

Suresh Venkat,

@Suresh, nie sądzę, że jest wystarczająco miejsca na to? Nie jestem pewien.

Tayfun Zapłać

Czy możesz całkowicie usunąć część „komentarz”? Nie sądzę, aby było to właściwe.

Jukka Suomela,

Połóż wszystko, co możesz, i usuń resztę. I opublikuj to w odpowiedzi Hucka. Nie należy wstawiać komentarza do odpowiedzi w pierwotnym pytaniu

Suresh Venkat,

Odpowiedzi:

Oto prosty argument, który pokazuje, że QP nie jest znany z PSPACE:

$QP \subseteq PSPACE$ $P \subsetneq QP \subseteq PSPACE$

To oddziela od , o którym nie wiadomo, że posiada, więc również nie może być znany z tego, że trzyma. $P$ $PSPACE$ $QP \subseteq PSPACE$

Rzeczywiście mamy , ale nie rozdziela dwóch klas przez THT (jak podano w pytaniu). $PSPACE \subseteq QP \Rightarrow PSPACE \subsetneq EXP$ $QP \nsubseteq PSPACE$

Huck Bennett
źródło