-2
$\begingroup$

Why $PSPACE != Dtime(2^n)$? I can not see how padding argument can help here, how can it be proven?

$\endgroup$

closed as off-topic by Kristoffer Arnsfelt Hansen, Marzio De Biasi, Jan Johannsen, Emil Jeřábek supports Monica, Gamow Oct 31 '18 at 10:24

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kristoffer Arnsfelt Hansen, Marzio De Biasi, Jan Johannsen, Emil Jeřábek supports Monica, Gamow
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ I don't understand. What is the factorial of PSPACE? $\endgroup$ – Jan Johannsen Oct 31 '18 at 9:45
  • $\begingroup$ @Jan Johannsen - I assume that it represents the "not equal ≠ " sign in C programming language $\endgroup$ – Avi Tal Oct 31 '18 at 10:24
3
$\begingroup$

If DTIME(2^n)=PSPACE then DTIME(2^poly)=PSPACE.

But, by the time hierarchy theorem, DTIME(2^n)⊊DTIME(2^poly)

$\endgroup$
  • 1
    $\begingroup$ Please don't answer off-topic questions. $\endgroup$ – Jan Johannsen Oct 31 '18 at 9:44
  • 4
    $\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$ – Yonatan N Oct 31 '18 at 15:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.