Question

Let ${\mathbf{CNF}}_{{}^H}\mathbf{=}\mathbf{\left\{}\mathbf{⟨}\mathbf{\varphi }\mathbf{⟩}\mathbf{\right|}\mathit{\varphi }$ is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal . Problem 7.25 asked you to show that CNFH ? P. Now give a log-space reduction from CIRCUIT VALUE to ${\mathbf{CNF}}_{{}^H}$ to conclude that ${\mathbf{CNF}}_{{}^H}$ is P-complete.

Short answer

The problem is solved by explaining a log-space reduction from$\text{CIRCUIT}-\text{VALUE}$ to$CN{F}_{{}^H}$ .Then concluding that $CN{F}_{{}^H}$ is P-Complete.

Step-by-step solution

Defining  CNFH statement

Consider the following$CN{F}_{{}^H}$ statement:

$CN{F}_{{}^H}=\text{{}<\varphi >|\varphi$ is a satisfiable cnf-formula, where every clause consists any number of literals} but is consists maximum one negated literal It is known that $CN{F}_{{}^H}\in P$.

Defining the CIRCUIT Evaluation

Now, consider the circuit evaluation $\text{CIRCUIT}-\text{VALUE}$ . For a circuit C and input string W , the value of C on W can be written as$C\left(W\right)$. Then, $\text{CIRCUIT}-\text{VALUE}$ is given by

$\text{CIRCUIT}-\text{VALUE}=\left\{⟨C,x⟩|C\text{\hspace{0.17em}\hspace{0.17em}isaBooleancircuitand\hspace{0.17em}\hspace{0.17em}}C\left(x\right)=1\right\}$

Understanding the required theorem

Consider the theorem,

Suppose $t\text{:}M\to M$ be a function, where$t\left(m\right)\ge m$.

If $w\epsilon \text{TIME}\left(t\left(m\right)\right)$, then the complexity of circuit A is given by $O\left(t^2\left(m\right)\right)$.

According to the above theorem,

On input , the production of a circuit takes place by the reduction. The process of reduction simulates the Turning Machine for in polynomial time. The itself can be taken as an input to the circuit.

The above theorem shows the way of reduction of a language w .

(Which is in P ) to $\text{CIRCUIT}-\text{VALUE}$.

A log space is used to carry out the reduction because the circuit produced by it contains a repetitive and a simple structure.

Hence, it shows that $\text{CIRCUIT}-\text{VALUE}$ is P complete and circuit produced by it has a repetitive structure. It shows that $\text{CIRCUIT}-\text{VALUE}$is P complete.

The above explanation gives a log-space reduction from $\text{CIRCUIT}-\text{VALUE}$to CNF .

Therefore, it is concluded that “CNFis P-complete.