Key question: why is having a SAT oracle less powerful than \(\text{SAT} \in P\)? What’s the role of a oracle?

with a SAT oracle…

We can solve NP problems because SAT is NP complete; we can solve coNP problems we can now finally just negate it.

polynomial hierarchy collapses if \(\text{SAT} \in \text{P}\)

We can solve \(\Sigma_{j}\) because we can peel off inner languages; for instance, for \(\Sigma_{2}\):

\begin{equation} x \in L \Leftrightarrow \exists w_{1} \forall w_{2} V\qty(x, w_{1}, w_{2}) = 1 \end{equation}

Key Sequence

Notation

New Concepts

• randomness
• some random algorithms
  • matrix multiplication verification
  • minimum spanning tree
  • undirected STCONN
  • PERFECT-MATCHING
  • polynomial identity testing
• randomized turing machine
  • BPTIME
  • RP

Important Results / Claims

• some questions of randomness
• RP in NP
• RP success amplifies

Questions

Interesting Factoids

Key Sequence

New Concepts

• randomized turing machine
• ZPP
• BPP in EXPTIME

Important Results / Claims

• BPP success amplication
• randomness hierarchy
• alternate (“deterministic”) definition of randomized TM

Questions

Interesting Factoids

Key Sequence

Notation

New Concepts

• circuits
• complexity measures of circuits
  • size (circuits)
  • depth (circuits)
• circuit family
  • p-uniform family
• uniform (complexity theory)
• size complexity

• P/poly

  • p-uniform P/poly is exactly P
• advice-taking TM

Important Results / Claims

• circuit’s contrasts with TMs
• p-uniform P/poly is exactly P
• expanding P towards P/poly

Questions

Interesting Factoids

Key Sequence

Notation

• circuit

New Concepts

Important Results / Claims

• BPP ⊂ P\Poly
• \(\text{BPP} \subseteq p / poly\)
• if \(\text{SAT} \in p / poly\), then polynomial hierarchy collapses to the second level; that is pi2=sigma2

Questions

Interesting Factoids