NP and Computational Intractability

• P is the set of yes/no problems that can be solved in polynomial time. Intuitively, P is the set of problems that can be solved quickly.
• NP is the set of yes/no problems with the following property: If the answer is yes, then there is a proof of this fact that can be checked in polynomial time.
• NP-Complete problem is 1) in NP and 2) every problem in NP can be reduced to it.
• NP-hard problems may be of any type: decision problems, search problems, optimization problems. A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H, L <= H

NP-Complete Problems

Proving further problems NP-Complete only requires a reduction from a single problem already known to be NP-Complete. Given a new problem X, here is the basic strategy for proving it is NP-Complete.

1. Prove that X is in NP
2. Choose a problem Y that is known to be NP-complete
3. Consider an arbitrary instance Sy of problem Y, and show how to construct, in polynomial time, an instance Sx of problem X, such that Sy and Sx have the same answer.

3SAT <= Independent Set <= Vertex Cover <= Set Cover Packing Problems
You are given a collection of objects, and you want to choose at least k of them; there are some conflicts among the objects, preventing you from choosing certain objects simultaneously.

1. Independent Set
2. Set Packing
   

Covering Problems
A natural contrast to packing problems, you are given a collection of objects, and you want to choose at most k of the objects that achieves a certain goal.

1. Vertex Cover
2. Set Cover

Partitioning Problems
Divide up a collection of objects into subsets so that each object appears in exactly one of the subsets.

1. Graph coloring, is at work whenever you are seeking to partition objects in the presence of conflicts, and conflicting objects are NOT allowed to go into the same set.

Sequencing Problems
Searching over the set of all permutations of a collection of objects.

1. Hamiltonian Cycle
2. Hamiltonian Path
3. Traveling Salesman

Numerical Problems

1. Subset Sum, the special case of the Knapsack Problem. Try reducing from Subset sum whenever one has a problem with weighted objects and the goal is to select objects conditioned on a constraint on the total weight of the objects selected.

Constraint Satisfaction Problems

1. 3-SAT. a useful starting point for reductions where none of the previous categories seem to fit naturally onto the problem being considered. There are two distinct ways to view an instance of 3-SAT, 1) a search over all the assignments to the variables, subject to the constraint that all clauses must be satisfied, and b) as a search over ways to choose a single term from each clause, subject to the constraint that one must not choose conflicting terms from different clauses.