A k-CNF formula is a conjunction (AND) of a set of clauses, where each clause is...

 

Transcribed Image Text:

A k-CNF formula is a conjunction (AND) of a set of clauses, where each clause is a disjunction (OR) of a set of exactly k literals. For example, (a vb v eV-dv-e)^(-avby cV-V-y)^(-vy Vevd Va) is a 5-CNF. The k-SAT problem asks if a k-CNF formula is satisfiable. In class we saw that 3-SAT is NP-hard. In contrast, 2-SAT is polynomially solvable. (a) Show that 4-SAT is NP-Complete (For partial credit in an exam, specify all the statements you need to conclude that 4-SAT is NP-complete even if you cannot prove them). (b) Describe a polynomial time algorithm to solve 1-SAT. A k-CNF formula is a conjunction (AND) of a set of clauses, where each clause is a disjunction (OR) of a set of exactly k literals. For example, (a vb v eV-dv-e)^(-avby cV-V-y)^(-vy Vevd Va) is a 5-CNF. The k-SAT problem asks if a k-CNF formula is satisfiable. In class we saw that 3-SAT is NP-hard. In contrast, 2-SAT is polynomially solvable. (a) Show that 4-SAT is NP-Complete (For partial credit in an exam, specify all the statements you need to conclude that 4-SAT is NP-complete even if you cannot prove them). (b) Describe a polynomial time algorithm to solve 1-SAT.

Answer rating: 100% (QA)

a To show that 4SAT is NPComplete we need to demonstrate two things 1 4SAT is in the class of NP pro... View the full answer