Chapter 7

Overview of NP-Completeness



Outcomes



Complexity Theory - Basic Question



Easy and Hard Problems



Polynomial and Exponential Time



Some Example Problems



P and NP



Classifying our Examples as P or NP



The Big Question



NP-Complete Problems


Reduction



Consequences of NP-Complete Problems



The First NP-Complete Problem



Showing That Other Problems are NP-Complete



Performance of NP Problems



Consequences of the class NP-Complete



Some NP-Complete Problems



Proving Cook's Theorem (Th 7.37)



Connection of Problems and Language Classes



NP-Hard Problems and the TSP



What to Do About Hard Problems?



ITEC 420 Course Page

Last modified on