In this in-depth interview with Avi Wigderson, Turing Award and Abel Prize winner, the fundamental question of P versus NP is explored as a profound inquiry into the limits of human knowledge. Wigderson explains that P represents problems solvable efficiently by computers, while NP encompasses problems for which solutions can be verified quickly, though finding those solutions may be hard. The crux of the P vs NP problem is whether every problem whose solution can be quickly verified can also be quickly solved. This question touches on whether we can, in principle, solve all problems we truly want to solve, impacting fields from medicine to cryptography. Wigderson expresses the prevailing intuition in the theoretical computer science community that P and NP are not equal, citing decades of unsuccessful attempts to find efficient algorithms for NP-complete problems and the inherent complexity of searching exponentially large solution spaces.
The discussion then delves into the practical aspects of NP-complete problems, such as protein folding and optimization, where exact solutions are often infeasible. Wigderson highlights that while these problems are theoretically hard, real-world instances often have additional structure that allows heuristic or approximate solutions to work effectively. He also explains the significance of approximation algorithms and the PCP theorem, which shows that even approximating solutions within certain bounds remains computationally hard. This leads to a broader overview of complexity classes beyond P and NP, emphasizing the rich “zoo” of classes that categorize problems based on various computational resources like time, space, and randomness, and the importance of reductions that relate the complexity of different problems.
Wigderson further discusses the role of randomness as a computational resource, explaining how randomized algorithms use random bits to achieve efficiency but also introduce probabilistic error. He elaborates on the challenges of obtaining high-quality randomness and the theory of pseudorandomness, which seeks to generate sequences that appear random to any efficient observer. The quality of randomness is thus relative to the computational power of the observer, a concept illustrated through thought experiments involving predicting coin tosses with varying levels of computational capability. This leads to the hardness versus randomness paradigm, which connects the existence of hard computational problems to the ability to derandomize algorithms, suggesting that randomness may not add as much power as once thought.
The interview also covers zero-knowledge proofs, a groundbreaking concept in cryptography where one party can prove knowledge of a solution without revealing any information about it. Wigderson explains the intuition behind zero-knowledge proofs using the example of graph coloring and how interactive protocols can convince a verifier of a claim’s truth without leaking knowledge. He emphasizes the universality of zero-knowledge proofs for all NP problems, relying on cryptographic assumptions like one-way functions. This concept has profound implications for secure computation and privacy-preserving protocols, demonstrating the deep interplay between complexity theory and cryptography.
Finally, Wigderson reflects on the impact of quantum computation on complexity theory and cryptography. Quantum computers, leveraging principles of quantum mechanics, can solve certain problems like integer factoring exponentially faster than classical computers, threatening current cryptographic systems. This has spurred research into quantum-resistant cryptographic assumptions and new complexity classes involving quantum interactive proofs. He highlights a remarkable recent result showing that quantum entangled provers can verify even undecidable problems, illustrating the profound and sometimes surprising consequences of extending classical computational models. Throughout, Wigderson underscores the dual nature of theoretical computer science as both a mathematical discipline and a study of computation, motivated by curiosity, modeling, and the pursuit of understanding the fundamental limits of what can be computed.
