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 :)

— 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,

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