All Questions
Tagged with separation logspace
1 question
4
votes
0
answers
98
views
Are there any non-relativized separations between $L$ and $PH$?
In one sense, $P$ vs. $PSPACE$ is the "easiest" first step to showing $P \neq NP$... and this is one you hear often about. In a different sense, you could take $L$ at one end and then $PH$ at the ...
- 856