Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$

  • 4
    $\begingroup$ cs.stackexchange.com/questions/35371/… $\endgroup$ – Laakeri Mar 29 at 11:50
  • 1
    $\begingroup$ The Hopcroft-Paul-Valiant theorem says that time-$T$ Turing machines can be simulated in space $O(T / \log T)$. I suppose that theorem could be interpreted as hinting that $\mathbf{P} = \mathbf{L}$ and $\mathbf{EXP} = \mathbf{PSPACE}$. (I think it seems much more likely that these classes are not equal, though.) $\endgroup$ – William Hoza Apr 2 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.