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