<p>Anything or evidence hinting that <span class="math-container">$$EXPTIME \subseteqq PSPACE$$</span>？</p>

CC BY-SA 4.0
2021-03-29T11:50:25.933Z
https://cs.stackexchange.com/questions/35371/why-do-we-believe-that-pspace-%E2%89%A0-exptime
Laakeri
CC BY-SA 4.0
2021-04-02T04:47:05.867Z
The [Hopcroft-Paul-Valiant theorem](https://www.csd.uwo.ca/~mmorenom/CS433-CS9624/Resources/p332-hopcroft.pdf) 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.)
William Hoza
<cc.complexity-theory><complexity-classes><exp-time-algorithms><pspace>
anything hinting that EXPTIME $\subseteqq$ PSPACE?
XL _At_Here_There
# anything hinting that EXPTIME $\subseteqq$ PSPACE?

(Asked by: username_0 on 2021-03-29)

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

**Tags:** cc.complexity-theory, complexity-classes, exp-time-algorithms, pspace
> **Comments:**
> **username_1**: https://cs.stackexchange.com/questions/35371/why-do-we-believe-that-pspace-%E2%89%A0-exptime  
> **username_2**: The [Hopcroft-Paul-Valiant theorem](https://www.csd.uwo.ca/~mmorenom/CS433-CS9624/Resources/p332-hopcroft.pdf) 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.)  

---

## 0 answers

