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

Key Sequence

Notation

New Concepts

• Interactive Proof
• IP(k)

Important Results / Claims

• An Anthropomorphic View of NP
• Graph Isomorphism is in NP
• IP = PSACE

Questions

Interesting Factoids

An Anthropomorphic View of NP

For some string \(x\), and language \(L\). We wonder:

\begin{equation} x \in^{?} L \end{equation}

We can consider NP as a two party game, whereby:

• prover: looks at \(x, L\), and sends some proof \(w\) for \(x \in L\)
• verifier: does some polytime computation, and either accepts or rejects

We want to make sure that this system follows the following patterns: