Part 4
NP Complete

Overview

Briefly, P is the class of problems that can be solved deterministically in polynomial time. Class P is important because (a) it is invariant over all reasonable models of computation and (b) practical problems in P have efficient (low-degree polynomial) algorithms. Important examples of problems in P include context-free language recognition, primarily testing, matrix multiplication and inversion, linear programming, finding shortest paths and minimal spanning trees in graphs, and finding convex hulls and Voronoi diagrams.

Briefly, NP is the class of problems that can be verified deterministically in polynomial time. Equivalently, NP is the class of problems that can be solved nondeterministically in polynomical time. The class NP is also invariant over all reasonable models of computation. Clearly, P ⊆ NP, but is not known whether or not P = NP.

Problem P₁ is polynomially reducible to problem P2 (P₁ ≤_PP₂) if there exists a polynomial-time algorithm that transforms every instance I₁ of P₁ to an instance I₂ of P₂ such that the answer to I₁ is ”yes” (I₁ P₁) if and only if the answer to I₂ is ”yes” (I₂ P₂).

Note. The relation ≤_P is transitive: P1 ≤_P P2 and P2 ≤_P P3 implies P1 ≤_P P3. This follows from the fact that the composition of two polynomial functions is another polynomial function.

Note. If P₁ ≤_PP₂ and P₂ P, then P₁ P. To solve an instance of P₁ in polynomial time, first transform it to an instance of P₂ in polynomial time, and then use the polynomial-time decision procedure for P₂. Note. If P₁ ≤_PP₂ and P₁ ⁄ P, then P₂ ⁄ P. This follows immediately from the previous note, and provides a way to prove that problems are impracticable (not in P). If P₁ ≤_PP₂, we say that P₂ is at least as hard as P₁.

Def. Problem P is NP-complete if:

1. P NP, and
2. Every problem P′ NP is polynomially reducible to P.

That is, a problem is NP-complete if it is in NP and it is at least as hard as every problem in NP. Note. If P₁ is NP-complete and P₁ ≤_PP₂, then P₂ is NP-complete. Note. If some NP-complete problem is in P, then P = NP. Proof. By an above note, every problem in NP is also in P, and, by definition, P ⊆ NP. This provides a potential way to settle the P = NP question. It shows that, if P≠NP, then the set P and the set of NP-complete problems are disjoint.

Algorithm C(s, t) is a certifier for problem X, if for an string s, s X, if and only if, there exists a string t, such that C(s, t) = True.

Polynomial time: Algorithm A runs in polynomial time, if for every string s, A(s) terminates in ≤ P(|s|) steps, where P() is a polynomial. So, all problems in P have polynomial time certifier.

Non-deterministic Polynomial: The class of decision problems that have a polynomial time certifier, such that

• C(s, t) runs in polynomial time.
• t, as output, is polynomially bounded in |s|, the input.

Strategy

There are three major kinds of strategies:

1. Reduction by simple equivalence
2. Reduction from simple case to general case
3. Reduction by encoding with Gadget.

List of NP Complete Problems

• Packing Problem
• Covering Problem
• Constraint Satisfaction Problem
• Sequencing (Cycling) Problem
• Partitioning Problem
• Numerical Problem

Bibliography