Notation

New Concepts

• Church-Turing Thesis
• turing machine
  • multi-tape TM theorem
• Time Complexity
  • P
  • NP: verifier formulation of NP
• non-determinism

Important Results / Claims

• Turing Machine as a universal algorithm
• properties of turing machines
• Church-Turing thesis as local steps
• time hierarchy theorem

Why stuff is great

• why TM is awesome
• why NP is awesome

Questions

Scratch

Let \(L \in P\), and \(M\) be the polytime TM that decides \(L\). Define \(M’\) to be \(M\) with \(q_{\text{accept}}\) and \(q_{\text{reject}}\) swapped. Fact: \(M’\) decides \(\neg L\).

Key Sequence

New Concepts

• Space Complexity
• PSPACE
• logspace
• STCONN

Important Results / Claims

• space complexity is tricky…
• “gold standard” for space complexity is \(O\qty(\log\qty(n))\)
• \(\text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(t\qty(n))\)
• \(\text{SPACE} \qty(s \qty(n)) \subseteq \text{TIME}\qty(2^{O\qty(s\qty(n))})\)
• space hierarchy theorem
• Space Time Hierachy

Questions

Interesting Factoids

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)