A student argues: 'Any polynomial-time algorithm can be simulated by polynomial-size circuits, so P and P/poly must be the same complexity class.' What is wrong with this reasoning?
AThe student is correct; P and P/poly are equivalent classes
BP ⊆ P/poly holds, but the reverse fails: circuit families are non-uniform and can hardwire information for each input length, allowing them to solve some undecidable problems that no Turing machine can
CCircuits cannot simulate Turing machines in general; the simulation only works for space-bounded computation
DThe simulation requires exponential-size circuits for polynomial-time algorithms
The student correctly identifies that P ⊆ P/poly — any poly-time TM can be unrolled into poly-size circuits. But the containment is strict. A circuit family is non-uniform: it can use a completely different circuit for each input length, hardwiring arbitrary finite information specific to that size. A Turing machine must use one finite program for all inputs. This non-uniformity lets circuit families 'solve' problems that no TM can, because the answer for inputs of length n can be baked into the circuit for length n without being computed.
Question 2 Multiple Choice
What does circuit depth measure, and how does it differ from circuit size?
ACircuit depth measures the total number of gates; circuit size measures the number of input wires
BCircuit depth measures the length of the longest input-to-output path (parallel time); circuit size measures the total number of gates (total work)
CCircuit depth measures the number of NOT gates; circuit size counts only AND and OR gates
DCircuit depth and size always differ by at most a polynomial factor, making them essentially equivalent
Size and depth measure different computational resources. Size = total gates = total work, analogous to sequential time. Depth = longest path from any input to output = the critical path, representing parallel time if all gates run simultaneously. A sequential chain of n gates has size n and depth n. A balanced binary tree of n gates has size n and depth log n. Problems in NC have both polynomial size and polylogarithmic depth (highly parallelizable); P-complete problems are in P but believed to require polynomial depth, making them inherently sequential.
Question 3 True / False
P/poly is a subset of P, because any problem solvable by polynomial-size circuits can also be solved by a polynomial-time Turing machine.
TTrue
FFalse
Answer: False
This reverses the correct relationship. P ⊆ P/poly, not the other way around. P/poly is strictly larger: it contains some undecidable problems, because circuit families can hardwire answers specific to each input length without computing them from a finite program. A Turing machine cannot exploit non-uniformity in this way. The undecidable language that contains exactly the binary encodings of circuits that accept their own length is a classic example of something in P/poly but outside any decidable class.
Question 4 True / False
Proving that some explicit Boolean function in NP requires super-polynomial circuit size would immediately prove P ≠ NP.
TTrue
FFalse
Answer: False
More precisely: showing NP ⊄ P/poly would imply P ≠ NP (since P ⊆ P/poly, if P = NP then NP ⊆ P/poly). But proving a super-polynomial lower bound for an arbitrary Boolean function doesn't directly address P vs NP — most functions require large circuits by a counting argument, but those functions aren't necessarily in NP. The challenge is finding an *explicit* function in NP that requires large circuits. The Karp-Lipton theorem gives the connection: if NP ⊆ P/poly, the polynomial hierarchy collapses to its second level, a widely disbelieved consequence providing indirect evidence against it.
Question 5 Short Answer
Explain why non-uniformity is both the power and the limitation of circuit complexity as a model of computation.
Think about your answer, then reveal below.
Model answer: Non-uniformity is the power because each input length can use a completely different circuit, hardwiring arbitrary finite information about inputs of that size. This lets circuit families solve problems that no Turing machine can — P/poly contains undecidable problems. It is also the limitation: a real computer program is uniform (one algorithm handles all input sizes), so circuit lower bounds in the non-uniform model don't directly translate to lower bounds for actual algorithms. If you want circuit lower bounds to imply P ≠ NP, you need to show that relevant NP functions lack efficient circuits even with full non-uniformity — which despite decades of effort has proved extremely difficult.
The tension is that non-uniformity seemingly restricts the model (circuits can't loop or recurse), which should make lower bounds easier to prove. But circuits are still enormously flexible — a different circuit per length is a powerful resource — and the best known lower bounds for general circuits fall far short of what would resolve P vs NP.