NP-Completeness

1.  Polynomial-Time Solvability

    --  A problem is polynomial-time solvable if there is an algorithm that correctly solves it in O(n^k ) time, for some constant k.

    --  P = the set of poly-time solvable problems.

        a) Cycle-free shortest paths in graphs with negative cycles is NP-Complete

        b) Knapsack [running time of our algorithm was (nW), but input length proportional to logW] is NP-complete

 

2.  Traveling Salesman Problem

    --  Input: Complete undirected graph with nonnegative edge costs.

    --  Output: A min-cost tour [i.e., a cycle that visits every vertex exactly once].

 

3.  Reductions

    --  Definition: Problem P1 reduces to problem P2 if: given a polynomial-time subroutine for P2, can use it to solve P1 in polynomial time.

    --  Computing the median reduces to sorting

    --  Detecting a cycle reduces to depth-first search

    --  All pairs shortest paths reduces to single-source shortest paths

 

4.  Completeness

    --  Suppose P1 reduces to P2, if P1 is not in P, then neither is P2. ==> P2 is at least as hard as P1.

    --  Let C = a set of problems. The problem P is C-complete if:

        (1) P in C 

        (2) everything in C reduces to P.

        That is: P is the hardest problem in all of C.

 

5.  Choice of the Class C

    --  Halting Problem: Given a program and an input for it, will it eventually halt?

    --  Fact: No algorithm, however slow, solves the Halting Problem.

    --  TSP definitely solvable in finite time (via brute-force search). TSP is as hard as all brute-force-solvable problems.

 

6.  The Class NP

    --  A problem is in NP if:

        (1) Solutions always have length polynomial in the input size

        (2) Purported solutions can be verified in polynomial time.

    -- Examples: 

        (1) Is there a TSP tour with length <= 1000?

        (2) Constraint satisfaction problems. (3-SAT)

 

7.  Interpretation of NP-Completeness

    --  Every problem in NP can be solved by brute-force search in exponential time. [Just check every candidate solution.]

    --  Fact: Vast majority of natural computational problems are in NP [Can recognize a solution]

    --  A polynomial-time algorithm for one NP-complete problem solves every problem in NP efficiently [implies that P=NP]

    --  NP-completeness is strong evidence of intractability.

 

8.  Proving that a problem P is NP-complete

    --  Find a known NP-complete problem P' (see Garey and Johnson, "Computers and Intractability")

    --  Prove that P' reduces to P

    --  implies that P at least as hard as P'

    --  P is NP-complete as well (assuming P is an NP problem)

 

9.  The P vs. NP Question

    --  NP : "Nondeterministic Polynomial"

        --  Widely conjectured: P<>NP

        --  (psychological) if P=NP, someone would have proved it by now

        --  (philosophical) if P=NP, then finding a proof always as easy as verifying one

        --  (mathematical) not known,  insane richness of the space of polynomial time algorithms

 

10.  Three Useful Strategies to Approach NP-Complete Problems

    --  Focus on computationally tractable special cases

        --  WIS in path graphs, trees and bounded tree widths graph.(NP-C in general graphs)

        --  Knapsack with polynomial size capacity (e.g., W = O(n))

        -- 2SAT (P) instead of 3SAT (NP-C)

        -- Vertex cover when optimal solution is small. (a smart kind of exaustive search)

    --  Heuristics - fast algorithms that are not always correct

        --  Greedy and dynamic programming-based heuristics for knapsack.

    --  Solve in exponential time but faster than brute-force search.

        -- Knapsack (O(n) instead of O(2^n))

        -- TSP (approximately 2^n instead of  n!)

        -- Vertex cover (n 2^OPT instead of n^OPT)