Question

Prove that 3 cnf sat is np complete​

Answer 1

3-CNF-SAT is NP-complete. Proof: ... So we just need to show CIRCUIT-SAT <p 3-CNF-SAT. From a circuit C made up of gates AND, OR, and NOT, and input variables in a set { 1 .. n}, we will construct a 3-CNF formula F that is satisfiable if and only if F is satisfiable.