We’re rewarding the question askers & reputations are being recalculated! Read more.

New answers tagged

3

You are right in noticing that the state space of an NL machine is only polynomially large (i.e. the number of reachable states is polynomial in the length $n$ of the input). A deterministic Logspace machine could enumerate all these states, and check whether one of them is accepting. But this is not enough. To faithfully simulate the NL machine, the ...


1

People don't know if NL=L or not yet. You showed that NL$\subseteq$ PSPACE, but it has nothing to do with L.


Top 50 recent answers are included