Complexity (23)
Michael L. Littman
December 8th, 1998
COMPLEXITY
Efficient Algorithms
Hard Problems
Degrees of Hardness
NP-COMPLETENESS
Decision Problems
Decision to Optimization
P
Nice Puzzle
NP
Good Guessing
Exponential Upperbound
NP-hardness
Reducibility
NP-Completeness
NP-COMPLETE PROBLEMS
Set Covering
Decision-Problem Version
Hard Problem
SAT
Hardness of Set Cover
Fine Points
Graph Coloring
Solving 3-colorability
Reduction
Colorability Complexity for Planar Graphs
PRACTICE PROBLEMS
Next:
COMPLEXITY