中文

P vs. NP, Zero-Knowledge Proofs, and the Embryonic Stage of Computation · Avi Wigderson

2026-06-21 · A faithful, transcript-grounded reading by PodLens

Original episode:https://youtu.be/5GUcvSAJcJw?si=IzMRyU2jYXu5fJOZ　·　Timestamps are clickable — they seek the player in place

computational complexityrandomnesszero-knowledge proofsquantum computationMIP* = REthe boundary of knowledge

What This Episode Is About

Avi Wigderson explores in depth the core propositions of computational complexity theory, arguing that P vs. NP is fundamentally a question about the boundary of human knowledge, and shares how theoretical computer science has reshaped our understanding of randomness, proof, and computation over the past several decades [02:22]. He explains in detail how randomness functions as a relative resource dependent on an observer's computational power (the Blum-Micali view) [55:14], the profound equivalence between hardness and pseudorandomness (P = BPP) [01:00:24], and the universality and practical application of zero-knowledge proofs [01:27:18]. He also discusses quantum computing's impact on classical cryptography (Shor's algorithm) [01:41:35], the breakthrough result of verifying uncomputable problems using entangled quantum provers (MIP* = RE) [01:50:15], and candidly notes that our understanding of the nature of computation remains at an extremely early "embryonic stage" [02:08:11].

Timeline Theme Map

Core Viewpoints

  1. The essence of P vs. NP is a question about the limits of human cognition. The problem asks whether we can efficiently solve all the hard problems we want to solve — that is, whether we can efficiently obtain all the truths we want to know.
  2. The class of NP problems covers nearly every problem worth pursuing as a human. In any domain of human exploration, the bare minimum requirement is that when someone presents a solution, we can quickly verify whether it's correct.
  3. Randomness is a relative computational resource, and its quality depends on the observer's computational power rather than any physical property. The same coin flip is random to a naked-eye observer, but completely predictable to a physicist connected to a supercomputer and an array of sensors.
  4. There is a profound complementary equivalence between hardness and randomness. If a problem genuinely requires an exponential-size circuit to solve, that hardness can be used to construct a pseudorandom generator that derandomizes any probabilistic algorithm — and the reverse holds too.
  5. Zero-knowledge proofs possess absolute universality. Any proposition with a mathematical proof inherently has a zero-knowledge interactive proof system that can verify it without revealing any of the proof's details.
  6. Introducing entangled quantum provers into an interactive proof system erases the boundary between computable and uncomputable. Harnessing the power of quantum entanglement, two non-communicating quantum provers can enable a polynomial-time verifier to decide problems as uncomputable as the halting problem.

Plain English Retelling

In the context of theoretical computer science, P vs. NP is absolutely not some simple math puzzle — it directly interrogates the boundary of human rationality. Avi Wigderson argues that NP encompasses every problem whose answer, once given, is easy to verify — which represents nearly the entirety of worthwhile human knowledge-seeking, whether you're looking for a mathematical proof, writing bug-free code, or cracking a cold case [02:22], [04:04]. If P equaled NP, finding an answer would become as easy as verifying one, meaning any unsolved cancer treatment or physics puzzle could be instantly searched out by a supercomputer — which obviously violates our basic intuition about the universe. In fact, the decades-long, worldwide failure of top scholars to find efficient algorithms for NP-complete problems is exactly this intuition playing out in reality [07:09].

This enormous gulf between searching and verifying even extends to how we think about proving truth itself. Traditionally, proving something requires fully displaying your argument. Zero-knowledge proofs break this convention in an extremely counterintuitive way: they let you convince someone you have an answer with absolute certainty, while revealing zero of your actual secret [01:27:18]. In the classic three-coloring map protocol, the prover randomly permutes the color names for each region and locks them down, allowing the verifier to randomly pick two adjacent regions to inspect — and each time, the verifier only ever sees two different random colors, learning nothing about the full coloring scheme of the entire map [01:35:08]. This interactive verification logic generalizes, via NP-completeness reductions, to every provable proposition, turning what was once a purely theoretical security toy into the core pillar of today's decentralized blockchain systems — completely overturning Avi Wigderson's own early prediction that it would "never be practically used" [02:03:17].

Randomness plays an equally counterintuitive role in this theoretical edifice — it's no longer some objectively existing physical noise in the universe, but purely a function of the observer's computational power [55:14]. If a probabilistic algorithm needs to consume a large number of truly random bits while running, then as long as the hard assumptions of computational complexity theory hold, we can construct a pseudorandom generator that strips out the necessary random resource entirely, achieving a deterministic conversion from BPP to P [01:00:24]. The quality of this pseudorandomness means that any observer bounded by polynomial-time computation can never distinguish it from a genuine coin flip — proving that hardness itself can serve as fuel for generating deterministic logic. Even though we still have absolutely no clue whether multiplication is genuinely harder than addition, this framework for converting a fundamental mathematical hardness into systemic robustness is already extremely solid [02:07:08].

The arrival of the quantum world further flattens the traditional divide between computable and uncomputable. Shor's algorithm's theoretical ability to efficiently crack large-integer factorization hangs like a sword over modern internet communication encryption systems, forcing research efforts worldwide to accelerate their shift toward lattice-based cryptosystems that are hard for quantum computers to easily break [01:41:35]. Even more shocking: when the mechanism of quantum entanglement from physics is introduced into interactive proof systems, a network of multiple entangled quantum provers displays an almost unimaginable expressive power — to the point that a problem as traditionally absolutely uncomputable as the Turing halting problem can be decided by an ordinary polynomial-time verifier, with the help of a multi-prover entangled system [01:50:15]. This suggests that the edifice of computation we thought we understood may rest on a foundation that's just a tiny piece of a much larger puzzle — we remain in the embryonic age of exploring the nature of computation [02:08:11].

Recommended Segments for Close Listening

Resonances with past episodes

A faithful reconstruction and plain-language retelling of the episode, generated by PodLens.

This is one source-grounded reading, not a replacement for the original. Every point is anchored to its source, so you can check it yourself — and corrections are welcome.