next up previous index CD Book Algorithms
Next: Lecture 20 - integer Up: No Title Previous: Lecture 18 - shortest

Lecture 19 - satisfiability

Listen To Part 21-7

The Theory of NP-Completeness

Several times this semester we have encountered problems for which we couldn't find efficient algorithms, such as the traveling salesman problem. We also couldn't prove an exponential time lower bound for the problem.  

By the early 1970s, literally hundreds of problems were stuck in this limbo. The theory of NP-Compleness, developed by Stephen Cook and Richard Karp, provided the tools to show that all of these problems were really the same problem.

Listen To Part 21-8

Polynomial vs. Exponential Time


n f(n) = n tex2html_wrap_inline15753 tex2html_wrap_inline15755 f(n) = n!
10 0.01 tex2html_wrap_inline15759 s 0.1 tex2html_wrap_inline15761 s 1 tex2html_wrap_inline15763 s 3.63 ms
20 0.02 tex2html_wrap_inline15765 s 0.4 tex2html_wrap_inline15767 s 1 ms 77.1 years
30 0.03 tex2html_wrap_inline15769 s 0.9 tex2html_wrap_inline15771 s 1 sec tex2html_wrap_inline15773 years
40 0.04 tex2html_wrap_inline15775 s 1.6 tex2html_wrap_inline15777 s 18.3 min
50 0.05 tex2html_wrap_inline15779 s 2.5 tex2html_wrap_inline15781 s 13 days
100 0.1 tex2html_wrap_inline15783 s 10 tex2html_wrap_inline15785 s tex2html_wrap_inline15787 years
1,000 1.00 tex2html_wrap_inline15789 s 1 ms

Listen To Part 21-9

The Main Idea

Suppose I gave you the following algorithm to solve the bandersnatch problem:   


Convert G to an instance of the Bo-billy problem Y.

Call the subroutine Bo-billy on Y to solve this instance.

Return the answer of Bo-billy(Y) as the answer to G.

Such a translation from instances of one type of problem to instances of another type such that answers are preserved is called a reduction.  

Now suppose my reduction translates G to Y in O(P(n)):

  1. If my Bo-billy subroutine ran in O(P'(n)) I can solve the Bandersnatch problem in O(P(n)+P'(n))
  2. If I know that tex2html_wrap_inline15797 is a lower-bound to compute Bandersnatch, then tex2html_wrap_inline15799 must be a lower-bound to compute Bo-billy.

The second argument is the idea we use to prove problems hard!

Listen To Part 21-10

Convex Hull and Sorting

A nice example of a reduction goes from sorting numbers to the convex hull problem:   

We must translate each number to a point. We can map x to tex2html_wrap_inline15801 .

Why? That means each integer is mapped to a point on the parabola tex2html_wrap_inline15803 .

Listen To Part 21-11

Since this parabola is convex, every point is on the convex hull. Further since neighboring points on the convex hull have neighboring x values, the convex hull returns the points sorted by x-coordinate, ie. the original numbers.


For each tex2html_wrap_inline15805 , create point tex2html_wrap_inline15807 .

Call subroutine convex-hull on this point set.

From the leftmost point in the hull,

read off the points from left to right.

Creating and reading off the points takes O(n) time.

What does this mean? Recall the sorting lower bound of tex2html_wrap_inline15811 . If we could do convex hull in better than tex2html_wrap_inline15813 , we could sort faster than tex2html_wrap_inline15815 - which violates our lower bound.

Thus convex hull must take tex2html_wrap_inline15817 as well!!!

Observe that any tex2html_wrap_inline15819 convex hull algorithm also gives us a complicated but correct tex2html_wrap_inline15821 sorting algorithm as well.

Listen To Part 22-2

What is a problem?

A problem is a general question, with parameters for the input and conditions on what is a satisfactory answer or solution.   

An instance is a problem with the input parameters specified.

Example: The Traveling Salesman

Problem: Given a weighted graph G, what tour tex2html_wrap_inline15823 minimizes tex2html_wrap_inline15825 .

Instance: tex2html_wrap_inline15827 , tex2html_wrap_inline15829 , tex2html_wrap_inline15831 , tex2html_wrap_inline15833 , tex2html_wrap_inline15835 , tex2html_wrap_inline15837

Solution: tex2html_wrap_inline15839 cost= 27

A problem with answers restricted to yes and no is called a decision problem. Most interesting optimization problems can be phrased as decision problems which capture the essence of the computation.  

Listen To Part 22-3

Example: The Traveling Salesman Decision Problem.  

Given a weighted graph G and integer k, does there exist a traveling salesman tour with cost tex2html_wrap_inline15841 k?

Using binary search and the decision version of the problem we can find the optimal TSP solution.

For convenience, from now on we will talk only about decision problems.

Note that there are many possible ways to encode the input graph: adjacency matrices, edge lists, etc. All reasonable encodings will be within polynomial size of each other.

The fact that we can ignore minor differences in encoding is important. We are concerned with the difference between algorithms which are polynomial and exponential in the size of the input.

Listen To Part 22-4


Consider the following logic problem:   

Instance: A set V of variables and a set of clauses C over V.

Question: Does there exist a satisfying truth assignment for C?

Example 1: tex2html_wrap_inline15843 and tex2html_wrap_inline15845

A clause is satisfied when at least one literal in it is TRUE. C is satisfied when tex2html_wrap_inline15847 TRUE.

Example 2: tex2html_wrap_inline15849 ,


Although you try, and you try, and you try and you try, you can get no satisfaction.  

There is no satisfying assigment since tex2html_wrap_inline15851 must be FALSE (third clause), so tex2html_wrap_inline15853 must be FALSE (second clause), but then the first clause is unsatisfiable!

For various reasons, it is known that satisfiability is a hard problem. Every top-notch algorithm expert in the world (and countless other, lesser lights) have tried to come up with a fast algorithm to test whether a given set of clauses is satisfiable, but all have failed.

Listen To Part 22-5

Further, many strange and impossible-to-believe things have been shown to be true if someone in fact did find a fast satisfiability algorithm.

Clearly, Satisfiability is in NP, since we can guess an assignment of TRUE, FALSE to the literals and check it in polynomial time.

Listen To Part 22-10

P versus NP

The precise distinction between whether a problem is in P or NP is somewhat technical, requiring formal language theory and Turing machines to state correctly.  

However, intuitively a problem is in P, (ie. polynomial) if it can be solved in time polynomial in the size of the input.

A problem is in NP if, given the answer, it is possible to verify that the answer is correct within time polynomial in the size of the input.  

Example P - Is there a path from to t in G of length less than k.

Example NP - Is there a TSP tour in G of length less than k. Given the tour, it is easy to add up the costs and convince me it is correct.

Example not NP - How many TSP tours are there in G of length less than k. Since there can be an exponential number of them, we cannot count them all in polynomial time.

Don't let this issue confuse you - the important idea here is of reductions as a way of proving hardness.

Listen To Part 22-7


Instance: A collection of clause C where each clause contains exactly 3 literals, boolean variable v.  

Question: Is there a truth assignment to v so that each clause is satisfied?

Note that this is a more restricted problem than SAT. If 3-SAT is NP-complete, it implies SAT is NP-complete but not visa-versa, perhaps long clauses are what makes SAT difficult?!

After all, 1-Sat is trivial!

Theorem: 3-SAT is NP-Complete

Proof: 3-SAT is NP - given an assignment, just check that each clause is covered. To prove it is complete, a reduction from tex2html_wrap_inline15855 must be provided. We will transform each clause independantly based on its length.

Suppose the clause tex2html_wrap_inline15857 contains k literals.

If none of the original variables in a clause are TRUE, there is no way to satisfy all of them using the additional variable:


But if any literal is TRUE, we have n-3 free variables and n-3 remaining 3-clauses, so we can satisfy each of them. tex2html_wrap_inline15893

Since any SAT solution will also satisfy the 3-SAT instance and any 3-SAT solution sets variables giving a SAT solution - the problems are equivallent. If there were n clauses and m total literals in the SAT instance, this transform takes O(m) time, so SAT and 3-SAT.

Note that a slight modification to this construction would prove 4-SAT, or 5-SAT,... also NP-complete. However, it breaks down when we try to use it for 2-SAT, since there is no way to stuff anything into the chain of clauses. It turns out that resolution gives a polynomial time algorithm for 2-SAT.

Listen To Part 22-9

Having at least 3-literals per clause is what makes the problem difficult. Now that we have shown 3-SAT is NP-complete, we may use it for further reductions. Since the set of 3-SAT instances is smaller and more regular than the SAT instances, it will be easier to use 3-SAT for future reductions. Remember the direction to reduction!


next up previous index CD Book Algorithms
Next: Lecture 20 - integer Up: No Title Previous: Lecture 18 - shortest

Mon Jun 2 09:21:39 EDT 1997