Lecture Notes for CS 512, Algorithm Design

19 October 1999, P and NP Problems

1. the pepsi siting problem

   1. put a pizza hut, pepsi, or frito-lay warehouse in each town, with no two directly adjacent towns having the same warehouse

   2. a recursive solution on an n-1 graph

   3. an exponential running time - can we do better

   4. the three-colorable graph 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 26 October 1999.