Question

Let ${\mathbf{CNF}}_{\mathbf{H}\mathbf{1}}\mathbf{=}\mathbf{\left\{}\mathbf{\right(}\mathbf{\varphi }\mathbf{\left)}\mathbf{\right|}\mathbf{\varphi }$ is a satisfiable cnf-formula where each clause contains any number of positive literals and at most one negated literal. Furthermore, each negated literal has at most one occurrence in $\mathbf{\varphi }$}. Show that ${\mathbf{CNF}}_{\mathbf{H}\mathbf{1}}$ is NL- complete.

Short answer

If and only if there is a positive phrase such that all variables are false, the formula is unsatisfiable. The NL-complete, reduce from directed reachability.

Encode all edges incoming to${\mathrm{x}}_{\mathrm{i}}$ by a clause of the form -${\mathrm{x}}_{\mathrm{i}}\mathrm{v}$

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: CNFH1  is NL complete:

There is only one instance of each negated literal. Let ${\mathrm{C}}_{\mathrm{i}}$stand for the sentence that contains$x_i$. Consider the graph with the variables as the vertices and $x_i$ connected to${\mathrm{x}}_{\mathrm{i}}$ . if ${\mathrm{x}}_{\mathrm{i}}$ is a member of ${\mathrm{C}}_{\mathrm{i}}$. This is an implication graph, which means that in order to derive that ${\mathrm{x}}_{\mathrm{i}}$is false from${\mathrm{C}}_{\mathrm{i}}$ , you must first deduce that ${\mathrm{x}}_{\mathrm{i}}$ was false from${\mathrm{C}}_{\mathrm{i}}$ .Prove that ${\mathrm{x}}_{\mathrm{i}}$ is false if the set of vertices accessible from${\mathrm{x}}_{\mathrm{i}}$ contains no directed cycle, which may be done in NL with$\mathrm{coNL}=\mathrm{NL}$ .

This demonstrates that the issue exists in the Netherlands. To prove that it is NL complete, reduce from directed reachability.