NP-Complete Problems

Guest lecture by K. Yue (November 2nd, 2001)

This is a brief summary of NP-Completeness and approximate algorithms. Read chapters 34 and 35 of the textbook (Corman, et. al.) Example details in this note will be covered in class.

Useful Links:

A compendium of NP optimization problems: a nice collection of NP Complete optimization problems.
Some notes on complexity by Dr. Dunne.

Classes of Problems

(1) P Problems (P: Polynomial): the set of all polynomially solvable problems.

P is closed under addition, multiplication and composition.
P is independent of particular formal models of computation or implementations.
Any problem not in P is hard.
A problem in P does not necessarily has an efficient algorithm.

(2) NP Problems (NP: Nondeterministic Polynomial): the set of all problems that can be solved if we always guess correctly what computation path we should follow.

Roughly speaking: include problems with exponential algorithms but have not proved that they cannot have polynomial time algorithms.
Alternate definition (e.g. Corman): the set of all problems those answers can be verified in polynomial time.
NP problems thus deal with decision problems as opposed to optimization problems.
P is a subset of NP, but we don't know whether P= NP.

(2') NP-hard problems: the set of all problems L such that any NP problems can be reduced to L in polynomial times.

Reducibility: A problem P1 is polynomial time reducible to P2 (P1 -> P2), if

There exists a one to one mapping from of input I1 of P1 to input I2 of P2.
P1(I1) if an only if P2(I2).

Note that if P1 -> P2, then

If P2 is in P, then P1 is in P, but
If P1 is in P, it does not follow that P2 is in P.

(2") NP-Complete problems: the set of problems that are both NP and NP-Hard.

NP-complete problems are equivalent in the sense that if one problem has an efficient algorithm (i.e. in P), then all NP-complete problems have efficient algorithms.

(3) Intractable problems: the set of problems that have been proven not to have polynomial algorithms.

(4) Undecidable problems: the set of problems that cannot be solved. No algorithm can be written for it.

Example: the halting problem: given arbitrary program and arbitrary input to the program, will the program eventually halt when the input is applied to the program?

In general, do not touch (3) and (4). They are for theoreticians.

Examples of non-determinism and decidability

(1) Nondeterministic finite state machines vs deterministic finite state machines.

Input alphabets: (0,1)

States: {q1, q2, q3, q4, q5, q6, q7, q8}

Transitions:

f(q1,1) = q2
f(q1,1) = q3
f(q1,e) = q4 (e: epsilon)
f(q2,0) = q6
f(q3,0) = q8
f(q3,0) = q7
f(q8,e) = q7
f(q4,1) = q5
f(q5,e) = q7

Start state: q1

Final states: {q6, q8}

(2) A nondeterministic algorithm for searching for an element Target in an array Keys(1..N).

i <- choice(1..N);
if Keys(i) == Target then
return I
end if;
return failure;

Note the 'magic' function choice which always return the right choice.

Time complexity: O(1).

(3) A nondeteministic algorithm for the k-clique problem.

The k-clique problem: given a graph(V,E), does it has a subgraph that is a clique (i.e. a complete graph where each node is connected to every other nodes)

Input: G(V,E) with |V| = N.

// step 1: solution formation.
// form a set of K vertices.
S <- {};
for i in 1..k loop
   j <-- choice(1..N);
   if j in S then return failure;
   S <-- S U {j};
end loop;

// step 2: solution verification.
check with S is a clique
for all pairs of (i,j) where i and j in S and i != j loop
   if (i,j) not in V then return failure;
end loop;
return success;

Time complexity = O(N*N).

Proving NP-Completeness

To prove that a problem P is NP-complete:

Method #1 (direct proof):

(a) P is in NP.
(b) All problems in NP-Complete can be reduced to P.

Example: Conjunctive Normal Form (CNF) Satisfiability problem (pp998-1002 of Corman et.al.)

Variable: true or false.
Literal: positive or negative literals.
Clause: literals or'ed together.
CNF: clauses and'ed together.

CNF- Satisfiability problem: given a CNF, are there assignments (of truth values) to variables in the CNF to make the CNF true.

Here is a proof of the NP-Completeness of the CNF Satisfiability problem by Dr. Dunne. It is not straightforward.

Method #2 (equally general but potentially easier):

(a) P is in NP.
(b) Find a problem P' that has already been proven to be in NP-Complete.
(c) Show that P' -> P.

Example: The k-clique problem.

(a) K-clique is in NP.
(b) CNF- Satisfiability is in NP-Complete.
(c) CNF- Satisfiability -> k-clique.

Method #3 (restriction; simple but not always available to all problems)

(a) P is in NP.
(b) Find a special case of P is in NP-Complete.

Example: Subgraph isomorphism: Given two graphs G(V1,E1) and H(V2,E2), does G contains a subgraph isomorphic to H? That is, can we find a subset V of V1 and E of E1 such that |V| = |V2| and |E| = |E2| and there exists a one to one function f: V2 -> V such that {u,v} in E2 if and only if {f(u), f(v)} is in E?

(a) Subgraph isomorphism is in NP.
(b) k-clique is a special case of subgraph isomorphism when H is a clique with k nodes.

Solving NP-Complete Problems

Given a NP-Complete Problems, what should you do?

Use brute force: may be the algorithm performance is acceptable for small input sizes.
Use time limit: terminates the algorithm after a time limit.
Use approximate algorithms for optimization problems: find a good solution, but not necessary the best solution.

How to measure the performance of an approximate algorithms?

P: Problem
I: Input
FS(I): the set of all feasible solution of P for input I.
V(I): FS(I) -> N; measure how good a feasible solution is.
opt(I): V(I) for the optimal solution for the input I.

For a feasible solution (provided by an approximate algorithm), A(I), we can measure:

r(A,I) = max(opt(I) / V((A(I)), V(A(I)) / opt(I))

Note that r(A,I) >= 1.

Thus, A(I) is optimal for I if r(A,I) = 1.

How good an approximate algorithm can be measure by worst case analysis with respect to opt(I) or input size.

R(A,m) = max {r(A,I) | opt(I) = m}

S(A,n) = max {r(A,I)|I is of size n}

Example: the knapsack problem.

Dr. Kwok-Bun Yue
Professor, Computer Science and Computer Information Systems
Chair, Division of Computing and Mathematics
University of Houston-Clear Lake
2700 Bay Area Boulevard
Houston, TX 77058
Yue's home page Yue's email yue@cl.uh.edu phone 281-283-3864