Section outline

  • December 20th, Friday (08:30-10:30)

    Intractability

    • Coding for Boolean expressions
    • Cook's theorem (proof of first part only)
    • Normal forms for Boolean expressions
    • CSAT problem and 3SAT problem
    • Definition of independent set and the IS problem
    • The problem IS is NP-complete
    • Definition of node cover and the NC problem
    • NC is NP-complete
    • Definition of a directed Hamiltonian circuit and the DHC problem
    • DHC is NP-complete
    • HC is NP-complete
    • TSP is NP-complete

    References

    • Hopcroft et al., cap. 10