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).


2

If SAT is in polylog space then PH should also be in polylog space, since the typical complete problems work under logspace reductions. By padding this implies e.g. Sigma3EXP is in PSPACE. So yes, in this case PSPACE is not in P/poly but moreover PSPACE has functions requiring maximum circuit complexity. At any rate the algorithmic hypothesis here is a lot ...


Top 50 recent answers are included