Design and analysis of Algorithms, 2nd Edition

17

Tractable and Non-Tractable Problems

Objectives

After reading this chapter, you should understand:

• The need for problem classification: Tractable and Intractable
• Upper and Lower Bounds
• Algorithmic Gap: Why the Lower Bound of a Problem and the Best Case of an Algorithm are Different
• The Class NP-Complete: Why it is a closed set
• Problem Transformation: One NP-complete problem to another
• NP-Completeness: How is it proved and Problem Reduction
• Non-Deterministic Algorithms
• The most famous open problem in Computer Science: P = NP ?
• Cook’s Theorem: First known proof of NPCompleteness
• Approximate Solutions – What it is about
• The complexity Classes and the meaning of Intractability
• Undecidable and Non-Computable problems
• The Halting Problem ...