Let CNFH = {| is a satisfiable cnf-formula where each clause contains any number of literals,
Question:
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 CNFH ∈ P. Now give a log-space reduction from CIRCUIT-VALUE to CNFH to conclude that CNFH is P complete.
Problem 7.25
Let CNFH = {〈ϕ〉| ϕ is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal}. Show that CNFH ∈ P.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Related Book For
Question Posted: