patternMinor
Show that NL ⊆ P
Viewed 0 times
showthatstackoverflow
Problem
Can somebody please explain this in simple terms. I don't understand Sipser's way of explaining it.
He says this is a corollary to PATH is NL-complete which I do not understand either.
Can somebody please explain everything in a simple manner to me?
Theorem 8.25 shows that any language in NL is log space reducible
to PATH. Therefore, any language in NL is polynomial-time reducible to PATH, which
in turn is in P, by Theorem 7.14. We know that every language that is polynomial-time reducible to a language in P is also in P, so the proof is complete.
He says this is a corollary to PATH is NL-complete which I do not understand either.
Can somebody please explain everything in a simple manner to me?
Theorem 8.25 shows that any language in NL is log space reducible
to PATH. Therefore, any language in NL is polynomial-time reducible to PATH, which
in turn is in P, by Theorem 7.14. We know that every language that is polynomial-time reducible to a language in P is also in P, so the proof is complete.
Solution
$\textsf{PATH}$ is in $\textsf{NL}$, because to solve it, you just need to keep in memory the current vertex you are in, and guess (non-deterministicaly) the next one on the path until you reach your destination. Since you keep the current vertex $v$, numbered from $0$ to $|V| - 1$, you need a memory space corresponding to the binary encoding of $v$, which is at most $1 + \log_2(|V| - 1)$. You also need to keep the potential adjacent vertex of $v$, next in the path.
All in all, a Turing Machine solving this problem would only need $O(\log |V|)$ additionnal space memory (the memory of the graph and of the starting vertex and the destination vertex of the path you are guessing are not considered in the memory used, because they are part of the input).
$\textsf{PATH}$ is $\textsf{NL}$-hard, because to solve any $\textsf{NL}$ problem, you have to determine if there exists a sequence of possible transitions from the initial configuration to an accepting configuration in the Turing Machine of the problem. If you consider a graph of the possible configurations (where there exists an edge from a configuration $\alpha$ to a configuration $\beta$ if and only if one can go from $\alpha$ to $\beta$ in one transition in the Turing Machine), then solving the $\textsf{NL}$ problem is the same as solving $\textsf{PATH}$ in the graph of possible configurations.
You then need to prove that the graph of configurations can be constructed in logarithmic additionnal space. This can be done, because if a non-deterministic Turing Machine works in space $s(n)$, then the number of possible configurations is $2^{O(s(n))}$. Considering the binary encoding of those configurations, one can determine if there exists an edge between two configurations in deterministic space $O(s(n))$.
Now, since $\textsf{PATH}$ is solvable in polynomial time (with a graph traversal algorithm, for example), that means that any $\textsf{NL}$ problem is solvable in polynomial time (via the $\textsf{NL}$-completude of $\textsf{PATH}$), so $\textsf{NL}\subseteq \textsf{P}$. This stands true, because if a Turing Machine uses $s(n)$ space memory, then it has at most $2^{O(s(n))}$ configurations, and exploring all of them takes time $2^{O(s(n))}$. Since $s(n) = \log n$ for problems in $\textsf{NL}$, the total time is indeed $n^{O(1)}$.
All in all, a Turing Machine solving this problem would only need $O(\log |V|)$ additionnal space memory (the memory of the graph and of the starting vertex and the destination vertex of the path you are guessing are not considered in the memory used, because they are part of the input).
$\textsf{PATH}$ is $\textsf{NL}$-hard, because to solve any $\textsf{NL}$ problem, you have to determine if there exists a sequence of possible transitions from the initial configuration to an accepting configuration in the Turing Machine of the problem. If you consider a graph of the possible configurations (where there exists an edge from a configuration $\alpha$ to a configuration $\beta$ if and only if one can go from $\alpha$ to $\beta$ in one transition in the Turing Machine), then solving the $\textsf{NL}$ problem is the same as solving $\textsf{PATH}$ in the graph of possible configurations.
You then need to prove that the graph of configurations can be constructed in logarithmic additionnal space. This can be done, because if a non-deterministic Turing Machine works in space $s(n)$, then the number of possible configurations is $2^{O(s(n))}$. Considering the binary encoding of those configurations, one can determine if there exists an edge between two configurations in deterministic space $O(s(n))$.
Now, since $\textsf{PATH}$ is solvable in polynomial time (with a graph traversal algorithm, for example), that means that any $\textsf{NL}$ problem is solvable in polynomial time (via the $\textsf{NL}$-completude of $\textsf{PATH}$), so $\textsf{NL}\subseteq \textsf{P}$. This stands true, because if a Turing Machine uses $s(n)$ space memory, then it has at most $2^{O(s(n))}$ configurations, and exploring all of them takes time $2^{O(s(n))}$. Since $s(n) = \log n$ for problems in $\textsf{NL}$, the total time is indeed $n^{O(1)}$.
Context
StackExchange Computer Science Q#138963, answer score: 2
Revisions (0)
No revisions yet.