Chapter 7

Overview of NP-Completeness


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


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