91Ó°ÊÓ

NL-complete is a complexity class in computational complexity theory that includes all languages that are complete for NL, a class of decision problems that can be handled by a nondeterministic Turing machine with a logarithmic amount of memory space.

Create a graph $\mathrm{G}$that occupies log space. In $\mathrm{G}$, choose a nondeterministic vertex x. Verify if $\mathrm{G}$ has both $\stackrel{\_\_}{\mathrm{x}},\mathrm{x}$ and $\stackrel{\_\_}{\mathrm{x}},\mathrm{x}$pathways using an NL algorithm, accept if both paths exit, else reject.

To demonstrate the NL-Hardness of $\stackrel{\_\_\_\_\_\_\_\_}{2\mathrm{SAT}}$, show that $\mathrm{PATH}{≤}_{\mathrm{L}}\stackrel{\_\_\_\_\_\_\_\_\_}{2\mathrm{SAT}}$. Given the formula $(\mathrm{G},\mathrm{s},\mathrm{t},\mathrm{a})$-2cnf, $\mathrm{ϕ}$such that $\mathrm{G}$ consists of s,t path if f is unsatiffiable. Allow $\mathrm{V}\left(\mathrm{G}\right)=\{\mathrm{s},\mathrm{t},{\mathrm{y}}_1,\mathrm{...}{\mathrm{y}}_{\mathrm{m}}\}$. The variable $\mathrm{x},{\mathrm{y}}_1,...{\mathrm{y}}_{\mathrm{m}}$ is made up of $\mathrm{m}+1$variables. The vertex s is identified with $\mathrm{x}$, while the vertex t is recognised with $\mathrm{x}$. This is how the construction of $\mathrm{ϕ}$is done