New answers tagged

8

This is equivalent to $LOGSPACE‚ȆNP$ (which is obviously open). The proof of that equivalence relativizes (at least under the usual oracle models). And there are oracles making $LOGSPACE = NP$ (the PSPACE-complete TQBF works) and making them not equal (the oracle separating P from NP works).


Top 50 recent answers are included