-2
$\begingroup$

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

$\endgroup$
  • 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.