For Turing Award winner, everything is computation and some problems are unsolvable
"It is one of the most fundamental intellectual questions ever asked," says Avi Wigderson, recipient of the 2024 ACM Turing Award, regarding the question of P = NP. "If everyone is wrong, and P equals NP, it has amazing consequences."
The Association for Computing Machinery (ACM) on Wednesday announced that it has awarded this year's A.M. Turing prize, often referred to as the Nobel Prize of computing, to computer scientist and mathematician Avi Wigderson of the Institute for Advanced Study in Princeton, New Jersey.
Wigderson was recognized for fundamental contributions that advanced what is known as the Theory of Computation, with particular distinction in "reshaping our understanding of the role of randomness in computation," and "decades of intellectual leadership in theoretical computer science," said the ACM.
Also: Algorithms soon will run your life - and ruin it, if trained incorrectly
Named for British mathematician and computer scientist Alan M. Turing, the award comes with a $1 million prize with financial support provided by Google.
Wigderson, the Herbert H. Maass Professor at the Institute, has demonstrated over decades a profound understanding of computation as being more than just machines. Computation is a phenomenon found throughout the universe.
"Computation is a really fundamental notion," said Wigderson in an interview with ZDNET. "It's not just algorithms in computers: everything computes."
"When you see a seashell on the beach, with some remarkable pattern, that was computed by extremely simple steps: It grew from one grain, and, locally, these grains computed neighboring grains, and were connected -- this really simple process, you evolve it, and you get some amazing patterns."
These simple rules of local, incremental change -- "which we know very well," said Wigderson -- "can create very complex phenomena." Computational examples abound. Computation is how the fertilized egg gets to be a human being, or how human cells divide throughout one's lifetime. "Also, gossip," added Wigderson. "When you tell something that was told to you, or on Facebook -- the way information evolves, these are computational questions that can be framed in complete computational models."
Awarding the Turing prize to Wigderson is especially apt because his field, the Theory of Computation, was begun by Turing in 1936 with Turing's landmark paper, "On Computable Numbers, With an Application to the Entscheidungsproblem."
Turing laid the groundwork for the extremely broad definition of computation as an evolution of an environment via local, incremental changes, where the "environment" can be human beings, galaxies, shells on the beach, information, or any number of phenomena.
Also: Jack Dongarra, who made supercomputers usable, awarded 2021 ACM Turing prize
Viewed through the lens of Turing, as advanced over decades by Wigderson and colleagues, every natural phenomenon is computation. "How termites build these castles, or the bees, who somehow know where to go and look for the honey -- they actually evolve to create, even though they have very small brain cells," explained Wigderson.
The award recognizes Wigderson specifically for his contribution to understanding the role randomness plays in computation. Conventional computers, from mainframes to iPhones, are "deterministic"; meaning, they follow a predictable pattern of steps. But many of the most intriguing examples of computation in nature involve elements of randomness, from the seashell to the flocking of starlings known as murmuration.
Wigderson and collaborators used the exploration of randomness to advance the understanding of what problems can and cannot be computed "efficiently." There are numerous problems in the world -- in science, math, and engineering -- for which there are no known efficient algorithms, meaning an algorithm that can operate in "polynomial time," rather than exponential time.
Also: Alan Turing's enduring legacy: 10 ideas beyond Enigma
For example, factorization of large integers into their prime factors doesn't have a known algorithm that can run in less than exponential time. But it's not enough to find such an algorithm; computer scientists and mathematicians want to prove, to know for certain, one way or another, whether there could exist a solution for such "hard" problems.
The three primary papers cited by the ACM form a sequence, a progression, Wigderson told ZDNET.
"The question was how powerful is randomness in algorithms," said Wigderson. Starting in the eighties, computer scientists had found many ways to use randomness as a route to efficient algorithms, "And so, it looked like randomness is very powerful."
"These works aimed to show that randomness is not so powerful," he said. Instead, Wigderson and colleagues developed pseudorandom number generators that could solve some hard problems in an efficient, deterministic way.
"In all these papers, you take a hard problem and you create a pseudorandom generator that can deterministically generate bits that look random, and you can replace random inputs in a probabilistic algorithm [and fashion] a deterministic one."
Also: Famous computer scientists
The weeding out of randomness, replacing it with a deterministic approach, culminated in the final paper with the most sophisticated pseudorandom generator. The lesson, noted Wigderson: "We could conclude that any polynomial-time probabilistic algorithm can be made a polynomial-time deterministic one."
A surprising side-effect of those discoveries is that if you can remove randomness from an algorithm, you can prove the hardness of the problem -- a striking back-door way to settle the question of whether a problem is or is not a hard one.
"Somehow, these two concepts [randomness and hardness], which are very different, are intimately connected," said Wigderson. "They're almost the same thing. Removing randomness from probabilistic algorithms, and proving hardness of computational problems are, sort-of, dual problems."
For those wishing to delve more deeply into the work on randomness, the papers are listed below. However, you can just read the chapter on randomness in Wigderson's large volume, "Math and Computation," which is available as a free download. If you skim that book, you'll be head and shoulders above most people at your next cocktail party.
- "Hardness vs. Randomness" (Co-authored with Noam Nisan)
Among other findings, this paper introduced a new type of pseudorandom generator, and proved that efficient deterministic simulation of randomized algorithms is possible under much weaker assumptions than previously known.
- "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (Co-authored with László Babai, Lance Fortnow, and Noam Nisan)
This paper used `hardness amplification' to demonstrate that bounded-error probabilistic polynomial time (BPP) can be simulated in subexponential time for infinitely many input lengths under weaker assumptions.
- "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (Co-authored with Russell Impagliazzo)
This paper introduces a stronger pseudo-random generator with essentially optimal hardness vs randomness trade-offs.
For Wigderson, 67, the delight of teasing out surprising connections was a driving impulse from an early age.
Also: AI in sixty seconds
"I always loved math from early childhood," said Wigderson. "My dad interested me in puzzles and stuff."
Wigderson graduated from Israel's Technion (Institute of Technology) and earned master's and PhD degrees in computer science from Princeton University. A moving talk about his experiences is offered in Wigderson's acceptance speech last year when he received an honorary doctorate from Technion.
"I really care about formalizing computational models," said Wigderson of what draws his interest, "like, if some cryptographic protocol is secure or some algorithm's running time is such and such.
"The fact that it deals with this fundamental notion, but it is actually a mathematical field, is to me, very precious."
Also: Nvidia gives AI supercomputer to students so they have the same power as big tech engineers
Among the achievements of which he is proudest, said Wigderson, is his work advancing what are called "zero-knowledge proofs," where information can be kept secret but two counterparties can nevertheless reach an understanding. "Let's say that I know something, I know who will win the election, and you don't believe me, and I'm trying to convince you [that I really do]. There's a way for me to convince you without telling you anything you didn't already know."
In fact, such a state of affairs is the root of public-key cryptography, where each party keeps hidden their private key but is able to convince the other they've authoritatively signed an electronic contract, for example. "It's a totally paradoxical notion," said Wigderson of such zero-knowledge proofs. "This is the kind of thing that blows your mind to think something like this could exist."
Wigderson's intellect balances delight with a keen sense of the underlying significance. The question of which problems are provably hard, for example, has great stakes for society.
Also: AI could have 20% chance of sentience in 10 years, says philosopher David Chalmers
As formulated in the 1970s, the phrase, "Does P = NP?", asks whether a problem whose solution can be verified could also, ultimately, be solved by a polynomial-time equation -- solved efficiently. If so, then a computer could likely be built to solve some of the world's seemingly intractable problems in practical time spans.
"It is one of the most fundamental intellectual questions ever asked," said Wigderson of P = NP. His personal conjecture, which is consensus in his field, is that P does not equal NP, meaning, some problems are beyond being solved efficiently.
"If everyone is wrong, and P equals NP, it has amazing consequences," said Wigderson. "Practically any problem you want to solve, you can solve efficiently -- anything; you could cure cancer."
However, "If P does not equal NP, the implications for things beyond our reach are fairly significant," said Wigderson. For one thing, it would mean that some elements of human thought, such as creativity, might well be beyond the reach of computers because there's no way to efficiently simulate the heuristics, the human sense of things that go into, for example, artistic creation.
But the glass is half-full, in another sense: If NP problems cannot be solved efficiently, it means that cryptography -- the entire basis of the modern economy -- is safe from being cracked, noted Wigderson.
Also: The new Turing test: Are you human?
Whether P does or does not equal NP is an open question. "I was hoping to see somebody prove it in my lifetime, now I doubt it," said Wigderson.
Nor is the quantum computer the easy answer to that impasse. "Think of a quantum computer: this doesn't exist," said Wigderson. "We don't know if it ever will exist" -- even though it is intensely theorized by IBM and Google and others.
If P = NP is an open problem, so, too, is the question of the moment: What can AI -- including "artificial general intelligence" machines -- do or not do to equal human thought? Certainly, the notion that everything in the universe computes implies AI should be able to achieve some measure of human ability.
Also: AI's true goal may no longer be intelligence
"We are carbon, and they are silicon, so the material is different, but the difficulties are on a psychological level, not on the operational level," is Wigderson's view. Already, AI has demonstrated it "can solve lots of problems that we didn't know how to solve before," said Wigderson. He knows "some prominent mathematicians who are starting to use these devices as collaborators" in theorem-proving and the like.
"What's more interesting to me is what they cannot do," he said. "What are the limits of this type of computer?" One of those limits is the relative paucity of data required to train AI models for some problems.
Also: Can generative AI solve computer science's greatest unsolved problem?
"For example, designing a new mathematical theory like relativity, or Maxwell [Maxwell's Equations] -- for these, there are many fewer examples, right? So, I think that this type of theoretical breakthrough will be harder for these machines because there isn't so much data."
For the many implications of P equaling or not equaling NP, Wigderson is content to let a new generation lead the way.
"I'm having fun with the postdocs at the institute, and they're all brilliant, and I'm collaborating with some of them, and just learning from the young ones," he said. "It's very nice to be in this situation surrounded by young people that keeps you learning."