Let CNFH = {| is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal}. Problem 7.25

Let CNFH = {〈ϕ〉| ϕ 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 CNF_H ∈ P. Now give a log-space reduction from CIRCUIT-VALUE to CNFH to conclude that CNFH is P complete.

Problem 7.25

Let CNF_H = {〈ϕ〉| ϕ is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal}. Show that CNF_H ∈ P.