NP-Completeness

Bart Massey

Classes, Problems, Instances

  • Problem: Collection of instances related by a problem description

  • Instance: A single input

  • Example:

      MEDIAN VALUE
    
      Instance: A nonempty collection V of n values, with
      a total order between values
    
      Solution: A value v drawn from V such that
      exactly n div 2 values in V are less than or equal to V
      and the remaining values in V are greater than or
      equal to V
    
  • Class: Collection of problems related by a common property

  • Classes are usually about time or space complexity

Decision Problem

  • Problem where the answer for a given instance is either true or false

  • Can transform non-decision problems into decision problems

      MEDIAN BOUND
    
      Instance: A nonempty collection V of n values, with
      a total order between values. A value k in V.
    
      Question: Are at least n div 2 values in V less than
      or equal to than k?
    
  • Classic method for optimization problems is binary search on size limit on output

    • Optimization Problem: Find a shortest path for the Traveling Salesperson

    • Decision Problem: Is there a path of length <= l for the Traveling Salesperson?

    • Binary Search: Keep doubling l until the answer is yes, then binary search between last two answers. If TSP is O(nk), then decision version is O(nk), since l is bounded by existence of relatively short tours (double-tree, see below)

P and NP

  • Polytime: O(nk) for some (any) k

  • Non-deterministic Polynomial Time: decision problem known to be in P for a nondeterministic machine

  • Examples: TSP, Movie Jobs

Nondeterministic Machine

  • Augment a computer (Turing Machine, traditionally) with a conditional branch that notionally

    • Executes both arms in parallel (no limit on parallelism)

    • Always picks the arm that will lead to deciding yes if if there is such an arm

  • If the NDTM returns yes, then answer yes

  • Problem is in NP if NDTM can produce yes in polytime on problems with a yes answer (thus no in polytime on problems with a no answer)

C-Hardness, C-Completeness

  • A problem L is hard for a complexity class C if L's complexity class is as hard as any problem in C

  • A problem L is polytime-hard for C if any instance I' of a problem L' in C can be solved in polytime given the solution of some instance I of L

  • If the problem is also in C, it is complete for C

P-Completeness

  • Example: The Circuit Value Problem

      CIRCUIT VALUE
    
      Instance: A binary encoding of a Boolean combinatorial
      circuit C composed of AND, OR, and NOT gates, inputs x1, x2,
      ..., xn, and a designated output y.
    
      Question: Is y=true on inputs x1, x2, ..., xn?
    
  • Clearly Circuit Value is in P

  • It is possible to prove that every instance of any problem L in P can be encoded as a Circuit Value instance polynomial in the size of the L-instance

  • Circuit Value is P-complete

NP-Completeness

  • Example: PROP Satisfiability

      PROP SAT
    
      Instance: A propositional formula with atoms X1..Xn
    
      Question: Is there an assignment of true/false to
      the atoms such that the formula evaluates to true?
    
  • Prop SAT is in NP, since one can write a polytime nondeterministic program that assigns true/false to the atoms of X1..Xn in a way that makes the formula true if there is any satisfying assignment (thus, can get UNSAT by running the program for long enough)

  • It is possible to prove that every instance of any decision problem L in P can be encoded as a Prop SAT instance polynomial in the size of the L-instance such that the SAT instance has a satisfying assignment iff the L instance answer is yes. (Cook's Theorem, 1971; also a Russian proof by Levin at roughly the same time.)

  • Prop SAT is in NP and NP-hard, so NP-complete. Problems known to be in P are in NP, but none are known to be NP-hard

  • If we could find a deterministic polytime algorithm for an NP-hard problem, then P = NP. Is there one? It's a mystery

Other NPC Problems: Reduction

  • Building an analogue of Cook's proof for Prop SAT for an arbitrary problem L in NP is quite difficult. Prop SAT was chosen specifically to make the proof easy

  • Alternative technique: Show that Prop SAT is reducible to L

    • Show that every SAT instance can be reencoded in polytime as an instance of L

    • This reencoding shows that if we could solve instances of L in polytime we could solve instances of any problem in NP in polytime

    • Thus L is NP-hard, and since it is in NP, NP-complete

Example: 3SAT

    PROP CNF 3SAT

    Instance: A propositional formula encoded in
    Conjunctive Normal Form, with atoms X1..Xn. No
    clause of the formula has more than three literals

    Question: Is there an assignment of true/false to
    the atoms such that the formula evaluates to true?
  • Can reduce SAT to 3SAT *

    • Represent the SAT instance as a parse tree of its boolean formula. Let yi be the output of node i with inputs as given

    • Write the equivalence as a conjunctive formula over the nodes. Each clause will have at most three atoms

    • Convert each clause to two 3CNF clauses by implication and positive-nand = negative-nor

    • Augment a short clause with copies of literals

    • This collection of clauses is satisfiable iff the original clause is satisfiable

    • Thus, we can transform any SAT instance to a 3SAT instance in polytime in such a way that the 3SAT instance is equivalent to the SAT instance

  • 3SAT is NP-hard and in NP, so is NP-Complete

  • Now we have two NPC problems, with 3SAT being a restriction of SAT

  • What about 2SAT? No, there is no known way to transform a SAT instance into a 2SAT instance in polytime. So 2SAT is not known to be NP-hard. (It might be, if P=NP.) There's a deterministic polytime solution to 2SAT (2SAT is in P), so this makes sense

The NPC Family

  • There are literally hundreds of problems that have been proven NPC by chains of reductions starting with SAT

  • Once you add a problem to NPC, you can reduce from it to prove other problems NPC

  • This is where the NPC proof of TSP and Movie Jobs comes from

  • Note that only decision problems can be NPC: the binary search trick is used a lot for optimization problems

Subset Sum is NPC, so Knapsack is

    KNAPSACK

    Instance: A collection L of n lengths. A bound B.
    A target k.

    Question: Is the a subcollection of L that adds up
    to less than B but more than k.



    SUBSET SUM

    Instance: A collection of n positive integers w1..wn and a
    and an integer target size s

    Question: Is there a subset of w1..wn that adds up to
    exactly s?
  • Subset Sum has been proven NPC by a chain of reductions

  • Reduce Subset Sum to Knapsack

    • For a Subset Sum instance (W, s), create a Knapsack of capacity s with items p1..pn whose weight and value are w1..wn and answer the question of whether there is a solution of weight s

    • It is easy to see that the answer is yes for the Knapsack instance iff it is yes for the Subset Sum instance

    • Knapsack is NPC

Why Should You Care?

  • Garey and Johnson's classic book on NPC starts with a story about your boss wanting you to find an efficient general algorithm for a problem, but you can't

  • Way better to tell your boss "I proved your problem NPC and so I won't find an efficient algorithm without winning a Turing Award" than "This problem is too hard for me"

"Practical Example:" Tentmates

  • Dennis Sasha, Dr. Dobb's Journal 1998

      TENTMATES
    
      Given: Set T of tents. Capacity function s: T →
      N+. Set C of campers, with |C| = sum(ran
      s). Preference function p: C × C → -10..10 where
      p(c1, c2) is the preference of c1 for c2 and
    
      forall c in C . p(c, c) = 0.
    
      Find: Assignment function a: C → T satisfying
    
      forall t in T . |{c | a(c) = t}| = s(t)
    
      and maximizing
    
      sum[c1, c2 in C, a(c1) = a(c2)] p(c1, c2)
    
  • So…maximizing happiness of tentmates

  • Can come up with good polytime approximations, and good search algorithms

  • But a polytime algorithm is elusive

  • Convert to a decision problem and reduce from k-Clique, which is known NPC

  • This is your final homework

What To Do If Your Problem Is NPC

  • Try to find an efficient algorithm for the largest instance sizes you expect to encounter

  • Try to find a restriction of your problem that is in P

  • Try to find a good approximation algorithm that is in P