Turing Award Winner: P vs NP, Zero-Knowledge Proofs, Quantum Computation | Avi Wigderson

Main Ideas

1. P vs. NP and the Limits of What We Can Know

P consists of problems that can be solved efficiently—roughly, in polynomial time. NP consists of problems for which a proposed solution can be checked efficiently.

Wigderson connects this distinction to many human pursuits: we search for answers we can recognize as valid, such as a mathematical proof, a scientific explanation, or an engineering design that meets its requirements. The question P = NP? asks whether every problem whose answer can be efficiently verified can also be efficiently solved. In that sense, it concerns the limits of what we can discover, not just how quickly computers run.

Wigderson’s intuition is that P and NP are different: finding a solution often seems harder than checking one, and decades of work have failed to find efficient algorithms for many NP-complete problems. He emphasizes, however, that these are intuitions, not proofs.

An efficient algorithm for NP-complete problems would be a world-changing breakthrough, providing efficient solutions to a vast range of problems that can be translated into one another.

2. Worst-Case Difficulty Versus Practical Instances

Complexity theory usually asks whether an algorithm works efficiently for every possible input of a given size. Real-world instances often have additional structure and may be much easier than worst-case inputs.

Protein-folding formulations and software-verification problems can be NP-hard in general, yet practical methods may work well on the instances encountered in applications. The simplex method illustrates this gap: it can take exponential time on specially constructed worst-case inputs while often performing very well in practice.

SAT solvers are widely useful partly because researchers have developed sophisticated heuristics for the structured formulas that arise in applications. Their success does not show that worst-case SAT is easy.

3. Approximation and the PCP Theorem

When exact optimization is too difficult, one option is to settle for an approximate answer—for example, a solution within a specified factor of optimal.

The PCP theorem and later refinements show that approximation can itself be computationally hard. For some constraint-satisfaction problems, even improving slightly on a natural baseline can be as hard as finding an exact solution.

For example, a random assignment to a typical three-literal Boolean constraint satisfies it with probability (7/8). For relevant problems, the PCP theorem and its refinements show that achieving even (7/8+\varepsilon), for arbitrarily small positive (\varepsilon), can remain NP-hard.

4. Complexity Classes, Reductions, and Why SAT Is Central

Complexity theory classifies problems by the resources needed to solve them, including time, memory or space, communication between parties, and parallel time. Some problems are not computable at all; among computable problems, complexity classes describe different resource limits.

Reductions translate one problem into another while preserving whether the answer is yes or no. If an NP-complete problem can be solved efficiently, reductions imply that every problem in NP can be solved efficiently.

SAT is central because computations are built from local steps. A proposed computation can be represented as a sequence of configurations, with local constraints checking that each step follows correctly from the previous one. Those constraints can be encoded as a Boolean formula.

The same idea explains why factoring can be reduced to SAT: a proposed pair of factors can be checked by multiplying them and confirming that their product is the input number.

5. Time and Space Are Distinct Resources

Space is at most time: a computation running for (t) steps cannot visit more than (t) memory locations. But the best achievable trade-off depends on the problem and the model of computation.

Wigderson describes a result by Ryan Williams showing that, in a general Turing-machine setting, a computation running in time (t) can be simulated using roughly (\sqrt{t}) space, at the cost of much more time.

He also describes surprising small-space techniques. Barrington’s theorem shows that certain computations can be carried out using constant space by encoding operations as small permutations whose order matters. This illustrates that information can be encoded in a sequence of operations, not just stored explicitly in memory.

6. Randomness as a Computational Resource

Randomized algorithms use random bits and may have a small probability of error. Randomness therefore has costs and qualities that can be studied like time or memory.

In theory, algorithms often assume perfect, independent random bits. Real sources—such as physical measurements, hardware, or deterministic sequences used as substitutes—may be biased or correlated.

Pseudorandomness asks whether a weaker or generated source is good enough for a particular algorithm. The relevant standard is whether that algorithm can distinguish the source from truly random bits. This leads to Wigderson’s formulation that the quality of randomness is “in the eye of the beholder”: it depends on the computational power of the observer. A source may look random to a limited observer but be predictable to a more powerful one.

Hardness versus randomness links two seemingly different ideas. Under suitable assumptions that some computational problems are genuinely hard, pseudorandom generators can make randomized algorithms deterministic. Conversely, the ability to remove randomness from certain algorithms can imply the existence of hard problems.

This computational notion differs from information-theoretic randomness. For tasks such as generating a cryptographic secret, the actual entropy matters; merely fooling a limited algorithm may not be sufficient.

7. Randomness Extraction from Weak Sources

Wigderson distinguishes pseudorandomness from randomness extraction, which aims to turn imperfect randomness into higher-quality randomness.

A weak source may contain entropy but also have unknown biases or correlations. An extractor processes the source to produce candidate strings that are close to uniform. In the setting Wigderson discusses, one can produce many candidate blocks so that most are good, even though it may be unknown which particular block is good. Repeating an algorithm across the blocks and taking a majority result can then be useful.

With several independent weak sources, one can combine them to increase entropy. Wigderson gives sum-product ideas as an example: if addition does not create many distinct values from a set, multiplication may create more, and vice versa. Such methods can help “purify” randomness, though they do not solve every extraction problem.

8. Zero-Knowledge Proofs

An interactive proof lets a prover and a verifier exchange messages, with the verifier using randomness to test a claim. The verifier may have a small chance of accepting a false claim, but this error can be reduced.

A zero-knowledge proof aims to convince the verifier that a claim is true while revealing no additional information about the prover’s secret or witness. Wigderson emphasizes its cryptographic value: someone may need to prove that they followed a protocol correctly or possess a valid secret without disclosing the secret itself.

He outlines a graph three-coloring example:

1. The prover commits to a color for every vertex, hiding the colors.
2. The verifier randomly chooses an edge.
3. The prover opens the commitments for that edge’s two endpoints.
4. The verifier checks that both colors are valid and different.
5. The protocol is repeated many times to make cheating unlikely.
6. To preserve zero knowledge, the prover randomly permutes the three color names in each round. The verifier sees two different colors but learns no information about the prover’s overall coloring.

The proof system can be extended to other NP claims by reducing them to graph coloring while translating a witness along with the instance. The protocol’s soundness error can be made exponentially small, though a false claim may not be ruled out with absolute certainty in a finite number of rounds.

9. Quantum Computation and Complexity Theory

A quantum computer follows quantum-mechanical rules, including superposition and interference. It can simulate randomized computation and may outperform classical computers on particular problems.

Peter Shor’s algorithms showed that quantum computers could factor integers and compute discrete logarithms efficiently. These results matter because many existing cryptographic systems rely on the assumed difficulty of those problems.

Building reliable quantum hardware is difficult because quantum states are highly sensitive to noise. At the same time, researchers are developing cryptographic assumptions and systems intended to withstand quantum attacks. Wigderson notes that the known quantum algorithms for factoring and discrete logarithms are special: they use structure related to finding periods. Other proposed hard problems, including lattice-based ones, are important candidates for quantum-resistant cryptography.

A striking theoretical result, MIP* = RE, concerns interactive proofs with multiple entangled quantum provers. It characterizes recursively enumerable languages, including problems that are undecidable by ordinary algorithms. Wigderson presents it as a surprising example of complexity theory producing tools with implications for mathematics and physics.

Results of this scale can take years to check. Wigderson describes mathematical verification as a community process involving scrutiny, correction of errors, and later expository work.

10. What Motivates Theoretical Computer Science

Wigderson describes theoretical computer science as both mathematical and computational: it creates formal models and proves theorems while studying what computation can accomplish and what resources it requires.

Modeling and defining problems are central activities, not merely preliminary steps. Different models can reveal different capabilities and lead to new mathematical questions.

Theoretical work is not always motivated by immediate applications, but ideas can later become useful in cryptography, coding theory, and other systems. Wigderson says he underestimated how practically important zero-knowledge proofs would become.

Major breakthroughs are rare. Much progress comes from incremental results, and research often involves many unsuccessful attempts. He advises aspiring researchers to pursue problems and areas they genuinely enjoy, experiment with different topics, and learn where their interests and strengths lie.

Speakers and Sources Featured

• Avi Wigderson — Interview guest; discusses complexity theory, randomness, zero-knowledge proofs, quantum computation, and research.
• Ryan Peterman — Interviewer and podcast host; also delivers the sponsor message and closing remarks.
• WorkOS — Sponsor featured in an advertisement read by the host.