patternMinor
Meaning of $NL$ Complexity Class
Viewed 0 times
meaningclasscomplexity
Problem
I am aware of the complexity classes $P$, $NP$ and $L$. But I am not clear what $NL$ or Non-deterministic Log Space intuitively means. The part what I am unclear about is what is the meaning of Non-deterministic Space?
A Turing machine in a $L$ case would read an input, read/write on the work tape that is logarithmic in size, update its internal state, move the read write head on the work-tape and read head on the input tape. And at appropriate time it halts.
What does Non-determinism on work tape mean and how does the Turing Machine behave. I am totally lost on this one? An intuitive explanation would help.
A Turing machine in a $L$ case would read an input, read/write on the work tape that is logarithmic in size, update its internal state, move the read write head on the work-tape and read head on the input tape. And at appropriate time it halts.
What does Non-determinism on work tape mean and how does the Turing Machine behave. I am totally lost on this one? An intuitive explanation would help.
Solution
Nondeterminism is not about tape or space. It is just a computational model.
One way of thinking of how a nondeterministic TM works is parallel computation. Given an input $x$, a nondeterministic TM may start many parallel (branches of) computation and wait for answers. If all branches terminate then the whole computation terminates. In addition if at least one of them terminates with YES then the TM accepts the input. In particular a nondeterministic TM may run exponentially many branches at the same time.
However a deterministic TM is not allowed to run more than one process (branch) at the same, so less powerful in terms of time. But in terms of decidability they are equivalent.
For example consider 3SAT problem with variables $x_1, \dots, x_n$. Then on nondeterministic TM we can check all $2^n$ settings of the variables at the same time, while on a deterministic TM we will have to check each settings one by one in sequence.
NOTE: unlike a deterministic TM a nondeterministic TM is a hypothetical abstract model which is not something we use in our everyday life.
Definition of space complexity for nondeterministic Turing machines:
If $M$is a nondeterministic TM where all branches halt on all inputs then its space complexity is the maximum number of tape cells it scans on any branch of its computation.
In particular if a TM scans at most $O(log(n))$ working tape cells on every input of length $n$ then we say its space complexity is logarithmic. It also worth noting that requiring $O(log(n))$ space does not restrict running time. A TM may decide in exponential time but still use logarithmic space.
Typically, when dealing with sublinear, $log(n)$, space bounds we use Turing machines with two tapes: input read only tape, and working tape which contributes to space complexity.
Then formally $L = SPACE(log(n))$. $L$ is the class of languages that are decidable in logarithmic space on a deterministic TM. That means that a deterministic TM decides using no more than log space. If we switch from a deterministic TM to a nondeterministic TM then we have $NL = NSPACE(log(n))$, that is, the class of languages that are decidable in logarithmic space on a nondeterministic TM.
Thus, meaning, or more formally members, of $NL$ complexity class is all languages decidable:
1) on nondeterministic two tape TM
2) using at most $ O(log(n))$ space on work tape.
Example: the language of the problem deciding for a graph whether or not there is a simple path between nodes $s$ and $t$. This language is in $ NL$ class, but if it is in $L$ class is unknown.
One way of thinking of how a nondeterministic TM works is parallel computation. Given an input $x$, a nondeterministic TM may start many parallel (branches of) computation and wait for answers. If all branches terminate then the whole computation terminates. In addition if at least one of them terminates with YES then the TM accepts the input. In particular a nondeterministic TM may run exponentially many branches at the same time.
However a deterministic TM is not allowed to run more than one process (branch) at the same, so less powerful in terms of time. But in terms of decidability they are equivalent.
For example consider 3SAT problem with variables $x_1, \dots, x_n$. Then on nondeterministic TM we can check all $2^n$ settings of the variables at the same time, while on a deterministic TM we will have to check each settings one by one in sequence.
NOTE: unlike a deterministic TM a nondeterministic TM is a hypothetical abstract model which is not something we use in our everyday life.
Definition of space complexity for nondeterministic Turing machines:
If $M$is a nondeterministic TM where all branches halt on all inputs then its space complexity is the maximum number of tape cells it scans on any branch of its computation.
In particular if a TM scans at most $O(log(n))$ working tape cells on every input of length $n$ then we say its space complexity is logarithmic. It also worth noting that requiring $O(log(n))$ space does not restrict running time. A TM may decide in exponential time but still use logarithmic space.
Typically, when dealing with sublinear, $log(n)$, space bounds we use Turing machines with two tapes: input read only tape, and working tape which contributes to space complexity.
Then formally $L = SPACE(log(n))$. $L$ is the class of languages that are decidable in logarithmic space on a deterministic TM. That means that a deterministic TM decides using no more than log space. If we switch from a deterministic TM to a nondeterministic TM then we have $NL = NSPACE(log(n))$, that is, the class of languages that are decidable in logarithmic space on a nondeterministic TM.
Thus, meaning, or more formally members, of $NL$ complexity class is all languages decidable:
1) on nondeterministic two tape TM
2) using at most $ O(log(n))$ space on work tape.
Example: the language of the problem deciding for a graph whether or not there is a simple path between nodes $s$ and $t$. This language is in $ NL$ class, but if it is in $L$ class is unknown.
Context
StackExchange Computer Science Q#77736, answer score: 7
Revisions (0)
No revisions yet.