Solution Found!
Solved: Let CNFH = {hi
Chapter , Problem 10.23(choose chapter or problem)
QUESTION:
Let CNFH = {hi| is a satisable cnf-formula where each clause contains any number of literals, but at most one negated literal}. 7.25 asked you to show that CNFH P. Now give a log-space reduction from CIRCUIT-VALUE to CNFH to conclude that CNFH is P-complete.
Questions & Answers
QUESTION:
Let CNFH = {hi| is a satisable cnf-formula where each clause contains any number of literals, but at most one negated literal}. 7.25 asked you to show that CNFH P. Now give a log-space reduction from CIRCUIT-VALUE to CNFH to conclude that CNFH is P-complete.
ANSWER:The log-space reduction from CIRCUIT-VALUE to CNFH is as follows:
Given a circuit C with n input bits, it is possible to construct, in log-space, a formula Q over these n variables in conjunctive normal form. Then, we can construct a satisfaction formula , F of the form:
F = (x1 ? x2 ? ......? xn) ? Q
We can also apply the technique of negation normal form