Homework Exercise 6

Due: by 2pm on Web 19 Nov
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

WARNING! Some browsers do not display the "complement" notation (overline) properly, e.g., "the complement of L is denoted L". If the second "L" in this sentence does not display with a bar on top, then please consult the ASCII version of the handout to make sure you can read the questions correctly.

  1. A propositional formula F is in "exact 4-CNF" if it is in 4-CNF (i.e., each clause of F contains exactly 4 literals) and in addition, each clause of F contains no repeated variable (negated or otherwise).

    Give a detailed proof that the following language is NP-complete.

    X4SAT = { <F> : F is a satisfiable formula in exact 4-CNF }

    For example:

    • (x4 ∨ x2 ∨ x1 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) does not belong to X4SAT — it is not in 4-CNF.

    • (x3 ∨ x2 ∨ x1 ∨ x3) ∧ (x3 ∨ x1 ∨ x2 ∨ x4) does not belong to X4SAT — it is not in exact 4-CNF because variable x3 is repeated in the first clause.

    • (x4 ∨ x2 ∨ x1 ∨ x3) ∧ (x2 ∨ x1 ∨ x2 ∨ x4) does not belong to X4SAT — it is not in exact 4-CNF because variable x2 is repeated in the second clause.

    • (x4 ∨ x2 ∨ x1 ∨ x3) ∧ (x3 ∨ x1 ∨ x2 ∨ x4) does belong to X4SAT — it is in exact 4-CNF and can be satisfied by setting x1 = true, x2 = false, x3 = false, x4 = false.

    Hint: To begin, read and understand the reduction CNF-SAT ≤p 3SAT posted on the course website.