Key Sequence

Notation

New Concepts

• ECLIQUE
• SMALLEST-CNF
• polynomial hierarchy

Important Results / Claims

• What Happens if P=NP
• polynomial hierarchy results
  • \(\text{PH} \subseteq \text{PSPACE}\)
  • \(\text{P} = \text{NP} \implies \text{P} = \text{PH}\)

Questions

Interesting Factoids