Why $PSPACE != Dtime(2^n)$? I can not see how padding argument can help here, how can it be proven?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ I don't understand. What is the factorial of PSPACE? $\endgroup$– Jan JohannsenOct 31, 2018 at 9:45
-
$\begingroup$ @Jan Johannsen - I assume that it represents the "not equal ≠ " sign in C programming language $\endgroup$– Avi TalOct 31, 2018 at 10:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
If DTIME(2^n)=PSPACE then DTIME(2^poly)=PSPACE.
But, by the time hierarchy theorem, DTIME(2^n)⊊DTIME(2^poly)
-
1$\begingroup$ Please don't answer off-topic questions. $\endgroup$ Oct 31, 2018 at 9:44
-
5$\begingroup$ Is there a meta discussion somewhere regarding this policy? Considering most off-topic questions are here by mistake (and presumably in good faith), I don't see how it hurts anyone to post answers before the question is migrated. $\endgroup$ Oct 31, 2018 at 15:49