Computing a Nash equilibrium is a hard problem (PPAD-complete, shown by Daskalakis, Goldberg and Papadimitriou in 2006): it is not NP-complete because a solution always exists by Nash's theorem, but it is at least as hard as any problem whose solution is guaranteed to exist; unwinding Nash's Kakutani fixed-point existence proof yields an algorithm that may follow an exponentially long trail before reaching the equilibrium.

factualpending

Speaker

Scott Aaronson

Evidence Quote

“if you try to actually unwind the existence proof into an actual algorithm to calculate the equilibrium then what you get is an algorithm that ends up taking exponential points”

Source

Scott Aaronson - Quantum Computing, Complexity, and Creativity— Dwarkesh Patel
Created: 6/13/2026, 7:00:25 PM

Your notes

Loading notes...