Description
1. Let DOUBLE-SAT be the language consisting of all Boolean formulas that
have at least two distinct satisfying assignments. Show that DOUBLESAT is NP-complete.
2. A Boolean formula is in DNF form (Disjunctive normal form) if it is an
OR of clauses: C1 ∨ C2 ∨ . . . ∨ Cm, where each clause Cj is an AND of
literals.
Let DNF-SAT be language consisting of Boolean formulas ⟨ϕ⟩ that are in
DNF form and are satisfiable. In other words, the goal is to decide if a
given formula in DNF form is satisfiable. Is DNF-SAT in P? Is it in NP?
Is it NP-complete?
3. A Boolean formula is in 2-CNF form if it is an AND of clauses: C1 ∧ C2 ∧
. . . ∧ Cm, where each clause Cj is an OR of exactly two literals.
Let 2-SAT or 2-CNF-SAT be the language consisting of satisfiable Boolean
formulas that are in 2-CNF form. Is 2-CNF in P? Is it in NP? Is it NPcomplete?
4. If P = NP, which are the languages that are NP-Complete?
5. Show that if P = NP, there is a polynomial time algorithm to find a
satisfying assignment to a 3-SAT formula if such an assignment exists.
6. Show that A ≤P B and B ≤P C ⇒ A ≤P C.
7. Show that a language L is co-NP complete if and only if L is NP-complete.
8. Show that NP ̸= co-NP =⇒ P ̸= NP.
9. The language EXACT-CLIQUE consists of all ⟨G, k⟩ where G is an undirected graph and k is a natural number such that the largest clique in G
is of size exactly k. Show that EXACT-CLIQUE ∈ Σ2 ∩ Π2.