Question

Show that 2SAT is NL-complete.

Short answer

The clauses of will be $\mathrm{x}\vee \mathrm{x}$and$\stackrel{\_\_}{\mathrm{u}}\vee \mathrm{v}$ for every edge$(\mathrm{u},\mathrm{v})$ of $\mathrm{G}$.

Both BFS and DFS take polynomial time of $\mathrm{o}(\mathrm{v}+\mathrm{E})$ time, where v=#vertices ans E # edges in G

Step-by-step solution

Step-1: NL complete

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.

Step-2: 2SAT is NL complete

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}{\le }_{\mathrm{L}}\stackrel{\_\_\_\_\_\_\_\_\_}{2\mathrm{SAT}}$. Given the formula $(\mathrm{G},\mathrm{s},\mathrm{t},\mathrm{a})$-2cnf, $\mathrm{\varphi }$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{\varphi }$is done