Tractable and Non-Tractable Problems
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 ...