Key Sequence

Notation

New Concepts

• STCONN
  • Savitch’s Algorithm
  • PATH
• NL and Non-Deterministic Space
  • problems in \(NL\)
  • \(NL \subseteq P\)
  • \(NL \subseteq \text{SPACE}\qty(\log^{2}\qty(n))\)
  • \(\text{NL} = \text{coNL}\)

Important Results / Claims

• STCONN is in NL

Questions

Interesting Factoids

Key Sequence

Notation

New Concepts

• coNL
• Immerman-Szelepscenyi Theorem

Important Results / Claims

• Immerman-Szelepscenyi Theorem
  • Proof of the Immerman-Szelepscenyi Theorem
• Certificates Based Intepretation of NL

Questions

Interesting Factoids

Key Sequence

Notation

• A Library of Languages

New Concepts

• coNP
• UNSAT
• coNP complete
• NP intersect coNP
• some languages
  • PERFECT-MATCHING
  • PRIMES
  • FACTORING

Important Results / Claims

• SAT is in NP
• if \(\text{P}= \text{NP}\), then \(\text{NP} = \text{coNP}\) (ARROW GOES ONE WAY)
  • notice also the contrapositive \(\text{NP} \neq \text{coNP} \implies P \neq NP\).
• UNSAT is coNP-complete
• Hall’s Theorem and Not Hall’s Theorem

Interesting Factoids

• \(L\) is NP complete IFF \(\neg L\) is coNP complete.
• some open problems…
  • does \(\text{NP} = \text{coNP}\)
  • does NP intersect coNP equal to P? (Does having efficiently checkable proofs for both pretense and absence in a set imply we can actually proof it efficiently.)

Edmond’s Conjectures

• \(\text{NP} \neq \text{coNP}\) “probably easy and not trilling” (which is very wrong)
• \(\text{NP} \cap \text{coNP} = P\) “trilling” (which is true)

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

Today: let’s smash and together. Recall:

Recall:

Consider a new quantifier: