*
We often use reductions to solve new problems based on problems we can already solve. For example, in an earlier worksheet, we saw a reduction from the Resident Hospital problem to the Stable Matching problem.n
1
But. . . there’s another way to use reductions. A more sinister way. We’ll illustrate this using a famous
problem from logic: Satisability.
1 Boolean Satisability
Boolean satisability (SAT) isas far as Computer Scientists knowa hard problem, in the sense that no-one knows of an algorithm to solve SAT that has worst-case polynomial runtime. In the version of SAT that we discuss here, you’re given a propositional logic expression like:
(x1 ∨x2 ∨x3 ∨x4)∧(x5)∧(x1)∧(x2 ∨x3 ∨x5)∧(x2 ∨x3).
You must determine whether any assignment of truth values to variables (the xi’s) makes the expression true, which we call satisfying the expression.
Formally, an instance of SAT is a logical statement that is a conjunction (an “and” denoted by ∧) of c clauses. Each clause is a disjunction (an “or” denoted by ∨) of one or more literals, and each literal is either a variable xi or its negation xi. For convenience, we’ll insist on using the variables x1, x2, . . . xn for some n, without skipping any. Given an instance I of SAT, we want to know: is the instance I satisable or not? The answer is either Yes or No, so we call this a decision problem.
1. Is the example SAT instance above satisable? If not, explain why not. If so, prove it by giving an assignment that makes the statement true.
CPSC 320: NP-completeness, SAT and 3SAT Solutions
*
1
Copyright Notice: UBC retains the rights to this document. You may not distribute this document without permission. Well, OK. Just another way.
SOLUTION:
Yes, this is satisable. Solving it by hand: we need x5 = T and x1 = F . Once x5 is true, then the last two clauses indicate that x2 and x3 have to have the same truth values. Assigning both true or both false will also handle the rst clause. So, for example: x1 = F,x2 = T,x3 = T,x4 = T,x5 = T is a truth assignment that satises the clause.
1
2
2.
For a SAT instance I, a truth assignment is a potential solution, and the truth assignment is a good solution if it satises instance I.
Suppose in addition to instance I you were given a truth assignment, say represented as an array T [1..n] where T [i] is true if and only if xi is set to true. How long would it take to certify that truth assignment T is good?
SOLUTION: We should be able to plug in the truth values to the clause literals and evaluate whether all clauses are true in time that is linear in the length of the instance I. We can scan the clauses from rst to last, and for each, check whether at least one literal is true. We can check the truth assignment to each literal in O(1) time by looking in the array. The truth assignment is good if and only if all clauses are satised.
Note: We’ve just described a certication (or verication) algorithm for SAT. A certication algorithm takes as input an instance of a problem, plus a potential solution, and checks whether or not the solution is good. If a decision problem has a certication algorithm that runs in polynomial time (as a function of the given instance size), the problem is in the class NP. So, we’ve just shown that SAT is in NP.
A brute force algorithm could make a list of the variables x1, . . . , xn in the problem, try every assign- ment of truth values to these variables, and return YES if any satises the expression or NO otherwise. Asymptotically, how many truth assignments might this algorithm try (in terms of n)?
SOLUTION: Brute force would need to try 2n dierent truth assignments in the worst case. (Note that trying one truth assignment may take more than constant time. If it takes linear time, as in our algorithm above, the brute force algorithm takes Ω(n2n) time to run, in the worst case!)
3-SAT and SAT
3.
The 3-SAT problem is just like SAT, except that every clause must be exactly of length 3. Let’s build a reduction from SAT to 3-SAT (so we’re solving SAT in terms of 3-SAT). We’ll map an instance I of SAT to an instance I′ of 3-SAT, working on one clause at a time. Importantly, for our reduction to work, I should be satisable if and only if I′ is satisable.
1. Suppose that I has a clause with two literal, say (x2 ∨ x3). To obtain I′ from I, we want to replace this clause by one or more clauses, while ensuring that I is satisable if and only if I′ is. How can we do this? Hint: introduce a new variable y.
SOLUTION: We replace (x2 ∨ x3) by the two clauses (x2 ∨ x3 ∨ y) and (x2 ∨ x2 ∨ y). A truth assignment that satises I must also satisfy I′ because clause x2 ∨ x3 appears in both clauses of I′. Also, any truth assignment that satises I′ must set one of x2, x3 to True, thus satisfying I, because no matter which values we assign to y, the literals in y in one of the two clauses will be false, requiring x2 ∨ x3 to be true.
2. What if I has a clause with only one literal, say (x5)? Hint: introduce two new variables y and z.
SOLUTION: To obtain I′ from I, we replace (x5) with the four clauses (x5 ∨ y ∨ y), (x5 ∨ y ∨ z), (x5 ∨ y ∨ z) and (x5 ∨ y ∨ z). A truth assignment that satises I must also satisfy I′ because variable x5 appears in every one of the four clauses of I′. Also, any truth assignment that satises I′ must set x5 to True, thus satisfying I, because no matter which values we assign to y and z, the literals in y and z in one of the four clauses will both be false, requiring x5 to be true.
2
3. Now suppose that I has a clause with four literals, say (x1 ∨ x2 ∨ x3 ∨ x4). What 3-SAT clauses will you put in I′ to replace this clause, so that I′ is satisable if and only if I is? Hints: Break the clause up somehow. Don’t try using de Morgan’s laws. Instead, create a brand new variable, say y, and integrate that into your new clauses.
SOLUTION: Replace the clause above by (x1 ∨ x2 ∨ y) ∧ (y ∨ x3 ∨ x4).
4. For your construction of part 3, show that if I is satisable then I′ must also be satisable (and
modify your construction if needed to ensure this).
SOLUTION: Suppose that I is satisable. Then in a truth assignment that satises I, at least one of the literals x1, x2, x3, or x4 must be true. If one of the rst two literals (i.e., x1 or x2) is true, then the rst of our two new clauses is satised. We can make sure that the second clause, and thus all of I′, is satised by choosing y to be false. Alternatively if neither of the rst two literals is true, then we set y to be true, to ensure that the rst of our two clauses is satised. We can rest assured that the second clause is also satised because at least one of x3, or x4 must be true.
5. Also for your construction of part 3, show that if I′ is satisable then I must also be satisable.
SOLUTION: Suppose that I′ is satisable. A truth assignment that satises I′, with y removed, must also satisfy I. Specically, if y is set to true in I′’s satisfying truth assignment, we know that at least one of x3 or x4 must be true (since xn+1 is false). And if y is set to false in the satisfying truth assignment, at least one of x1 or x2 must be true. Either way, our original clause (x1 ∨ x2 ∨ x3 ∨ x4) must be true, and since all other clauses of I and I′ are identical, all other clauses of I must be satised too.
6. Extend your 4-literal clause plan above to a 5-literal clause like (x1 ∨ x2 ∨ x3 ∨ x4 ∨ x5). SOLUTION:
We can introduce two new variables, say y and z, and replace the above 5-literal clause by (x1 ∨x2 ∨y)∧(y∨∨x3 ∨z)∧(z∨x4 ∨x5).
7. Show, by lling in the blanks below, how you would transform any clause with k > 3 literals (l1 ∨l2 ∨…∨lk)
into clauses with three literals (keeping in mind overall reduction correctness). You can use new variables that have not already been “used up”, starting with xi+1 (where i ≥ n). How many clauses do you get? What would be the runtime of an algorithm to do this, as a function of k?
SOLUTION:
(l1 ∨l2 ∨xi+1)∧(x ̄i+1 ∨l3 ∨xi+2)∧(x ̄i+2 ∨l4 ∨xi+3)∧… ∧ (xi+(j−2) ∨ lj ∨ xi+(j−1)) ∧ . . .
. . . ∧ (x ̄i+(k−4) ∨ lk−2 ∨ xi+(k−3) ∧ (x ̄i+(k−3) ∨ lk−1 ∨ lk)
There are k − 2 new clauses in total, using k − 3 new variables xi+1, xi+1, . . . , xi+(k−3) to “link” the
clauses together. Overall, an algorithm to do this takes time Θ(k).
8. Let’s use the name Transform-Clause to refer to the algorithm for transforming a clause, as described in part 7. Suppose that I′ is obtained from I by transforming clause (l1 ∨ l2 . . . ∨ lk) using algorithm Transform-Clause. Explain why I is satisable if and only if I′ is satisable.
3
SOLUTION: This generalizes our arguments in parts 4 and 5
If direction: First suppose that I is satisable, and choose a satisfying truth assignment to the variables x1 . . . xn . We need to extend this to a satisfying truth assignment for I ′ , by assigning truth values to the newly created variables xi+1, . . . xi+(k−3).
Suppose that lj is the rst literal in the clause (l1 ∨ l2 . . . ∨ lk ) which is true with respect to the chosen truth assignment. Then we set xi, . . . , xi+(j−2) to true. These ensure that all clauses created before clause
(xi+(j−2) ∨ lj ∨ xi+(j−1))
are true. Literal lj ensures that clause (xi+(j−2) ∨ lj ∨ xi+(j−1)) is true. So, we can set the remaining newly created variables xi+(j−1),…,xi+(k−3), to false, ensuring that the remaining newly created clauses are true. This ensures that all clauses in I′ are true.
Only if direction: Conversely suppose that I′ is satisable. A truth assignment obtained by remov- ing the newly created variables from a satisfying truth assignment of I′ must satisfy all clauses of I other than (l1 ∨ l2 . . . ∨ lk), since all of these clauses are also in I′.
Suppose that (l1 ∨ l2 . . . ∨ lk ) is not satised by the chosen truth assignment. Then all of the li are false. In this case, in the truth assignment satisfying I′, it must be that all of xi+1, . . . , xi+(k−3) are true, in order to satisfy the rst k − 3 newly created clauses. In this case, the last clause, namely (xi+(k−3) ∨ lk−1 ∨ lk), will not be satised. This contradicts the fact that I′ is satised by the chosen truth assignment, and so we conclude that (l1 ∨ l2 . . . ∨ lk ) is indeed satised by the chosen truth assignment.
9. Give a reduction from SAT to 3-SAT. Recall that a reduction consists of two algorithms that “connect” one problem to another, as in the diagram from page 1.
SOLUTION:
Transform instance algorithm: This algorithm converts an instance I of SAT to an instance I′ of 3-SAT, working clause by clause, by calling the Transform-Clause algorithm described earlier on clauses of size greater than three, and using the transformations of parts 1 and 2 for clauses of sizes one and two respectively.
For instance:
SAT instance
X3∨X5 ⇒ X1 ∨X2 ∨X4 ∨X5 ⇒
X4 ⇒
X1 ∨X2 ∨X3 ∨X4 ∨X5 ∨X6 ⇒
3SAT instance
X3 ∨ X5 ∨ Y1 X3 ∨X5 ∨Y1
X1 ∨ X2 ∨ Y2 Y2 ∨X4 ∨X5
X 4 ∨ Y 3 ∨ Y 4 X 4 ∨ Y 3 ∨ Y 4 X4 ∨ Y3 ∨ Y4 X 4 ∨ Y 3 ∨ Y 4
X 1 ∨ X 2 ∨ Y 5 Y 5 ∨ X 3 ∨ Y 6 Y6 ∨ X4 ∨ Y7 Y 7 ∨ X 5 ∨ X 6
4
Transform solution algorithm: This algorithm to transform a solution (YES or NO) to the 3-SAT instance I′ back to a solution for I simply uses the exact same solution (YES OR NO).
Algorithm SAT-to-3-SAT(I) takes time linear in the length of I, and the algorithm to translate the solution back takes O(1) time.
Why is the reduction correct?
SOLUTION: We’ve shown in the previous parts that when we transform clauses with one literal, two literals, or at least four literals, we preserve satisability: I is satisable if and only if I′ is. Since our algorithm transforms one clause at a time, it preserves satisability at every step, so the nal 3-SAT instance I′ is satisable if and only if I is. As a result, the second algorithm that uses the solution for I′ as the solution for I produes the correct answer for I.
3
Here, consider a reduction from problem A to problem B, as illustrated in the gure of page 1.
1. SCENARIO #1 (how we’ve used reductions prior to this worksheet): Say our reduction’s two algorithms take O(f(n)) time and the black box solver for B also takes O(f(n)) time. What can we say about the running time to solve problem A?
SOLUTION: In this scenario, the reduction and the solution to problem B problem together yield an O(f(n)) solution to problem A. (This is how we’d normally use reductions in practice!)
2. SCENARIO #2 (what we usually think of NP-completeness as meaning): Say our reduc- tion’s two algorithms take O(g(n)) time and we know that there is no algorithm for problem A that runs in O(g(n)) time. What do we know about the running time for problem B? Why?
SOLUTION: In this situation, there canot be an algorithm for problem B that runs in O(g(n)) time. Why not? Well, say there were, then as in the previous part, we could use that to generate an O(g(n)) solution for problem A, but we said no such algorithm exists!
If we assume P ̸= NP, this is how we use reductions in an NP-completeness proof. (Although our use is technically more similar to what we do in the next part!)
3. SCENARIO #3 (what NP-completeness technically means): Say that we know (which we do) that if SAT can be solved in polynomial time, then any problem in the large set called “NP” can also be solved in polynomial time. What does our reduction from SAT to 3-SAT tell us? Why?
SOLUTION: It tells us that if 3-SAT can be solved in polynomial time, then so too can any problem in NP be solved in polynomial time.
10.
What does a reduction tell us?
5