New answers tagged turing-machines
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
