Chapter 7: NP Completeness

Chapter 7: NP Completeness

Goal of Chapter 3

Def. 7.1: Running Time or Time Complexity of a TM

Def. 7.2: Big O Time Complexity (Informal)

Polynomial and Exponential Time Complexity

Theorem 7.8: Time Complexity of Multitape Machines

Def. 7.9: Running time for a Nondeterministic Decider TM

Theorem 7.11: Nondeterministic and Deterministic TM Running Times

Def. 7.12: The Class P

Class P Example: PATH

Proving that L(M) is in P

Class P Example 2: RELPRIME

Class P Example 3: Every CFL ∈ P