Lecture Notes for CS 512, Algorithm Design

15 March 1999, P and NP Problems

1. the greedy heirs problem.

   1. the estate { x₀, x₁, ... x_n }, item i costs c(x_i)

   2. evenly divide the estate between dick and jane

   3. a recursive solution on an n-1 element set

   4. an exponential running time - can we do better

   5. the set partition problem.

2. tractable vs. intractable problems

   1. polynomial problems are tractable - even for large exponent

   2. non-polynomial problems are intractable

   3. can intractable problems be made tractable - do they have polynomial solutions

   4. nobody knows, but the thinking is they can't and they don't

3. the nondeterministic model of computation

   1. the choice operator - either take them all, or take the correct one

   2. polynomial down to a suspected solution, polynomial up to check the solution

   3. NP problems

4. problems and instances, decision problems - inputs and outputs; particular inputs and outputs, yes-no answers

5. reductions

   1. problem instance reductions, or translations

      1. polynomial

      2. a solution in one is a solution in the other, in both directions

   2. algorithms in the target language become algorithms in the source language

   3. polynomially equivalent problems, transitive reductions

   4. reductions and the lower bound

6. np structure

   1. np-hard problems - at least as hard as any np problem

   2. np-complete problems - it is an np problem

   3. use transitivity to translate an np-complete problem to the new problem

   4. cook's theorem - the satisfiability problem (SAT) is np-complete

7. some reductions

   1. vertex cover to clique

      1. compliment graphs

      2. k clique means |V| - k compliment cover

      3. k compliment cover means |V| - k clique

   2. dominating set to vertex cover

      1. triangulate edges

      2. dominating set to triangulated cover set

      3. triangulated cover set to dominating set

This page last modified on 21 March 2000.