4 minutes reading time
There are few things in life as vexing as the unsolved.
Simplicity, complexity, randomness, spectra, fields. Standalone words which, without context, provide no motivation for deeper consideration. But what if these words held a key that would unravel even the most intractable of problems?
On May 4, 1971 Stephen Cook published a 7-page paper that revolutionized the field of computer science.
In the paper, Cook laid the foundation for complexity theory while studying the polynomial reducibility of the determination of combined logical statements called tautologies. Cook proved that the determination of 'tautologyhood' (the truthiness of a statement) was equivalently difficult to determining if one graph was isomorphic to a subgraph of a different graph. In 1973, Leonid Levin would independently formulate the problem. This problem would later become known as P ?≠ NP, and was one of seven Millenium Problems selected by the Clay Institute, each of which promised a prize of one million dollars to the author of a valid solution.
It is here we will begin to pull at the threads of the impossible.
Why P ?≠ NP? Well, if P, the set of polynomial time reducible algorithms, were equivalent to NP, the set of nondeterministic-polynomial time algorithms, then many real world optimization problems would become trivial to solve. New drugs; improved sensing technologies; and perhaps the most alarming, the nullification of many cryptographic standards. It is commonly believed that P ≠ NP. But, there have been isolated instances of problem misclassification before. In 2004, Agrawal, Kayal, and Saxena published "PRIMES is in P," demonstrating a previously believed NP problem to have a deterministic polynomial time algorithm.
Practically speaking, it is not always necessary to derive a deterministic polynomial time algorithm for a problem. Often, it is entirely sufficient to use some kind of approximation technique instead. Even though you may not reach a globally optimal solution in all cases, it is usually possible to find a reasonably good solution - sometimes even with guaranteed bounds on time, memory, and error. The fields of AI and Scientific Computing exist to develop and apply such methods.
In the 2000s, two separate research efforts emerged which made significant contributions to the theory and application of approximation methods. The first group consisted of researchers like Terrence Tao, Emmanuel Candes, Justin Romberg, David Donoho, and Richard Baraniuk. This group applied results from random matrix theory to signal processing for the purpose of sparse signal recovery. Popularized as the field of 'compressed sensing' this work revolutionized medical image processing by greatly reducing the time it took to acquire a set of measurements. This same technology has also been applied in other domains such as Astronomy and Remote Sensing. Tao has a blog post which provides an approachable though likely outdated overview of the topic.
The second research effort originated in Richard Sutton's lab at The University of Alberta where learned heuristic search techniques were applied to combinatorial games, like Chess, Go, and Shogi. David Silver's university research went on to form the basis of Google Deepmind's Alphazero model. With co-contributors Demis Hassabis, Aja Huang, Oriol Vinyals, Ilya Sutskever, and many more. The application of Monte Carlo Tree Search to games later lead to the development of the Alphafold model which discovered a state of the art solution to the protein folding problem - resulting in a Nobel Prize for Demis Hassabis and John Jumper. Additionally, Sutton and Barto recently won a Turing award for their work on reinforcement learning.
For problems in NP, we would like to learn transition functions for nondeterministic Turing machines in a way which solves these problems in polynomial time. Perhaps just as important, we would like to know what physical computing paradigms can be utilized to accelerate implementations of these models? Even if it is difficult for a model to learn a provably optimal transition function, or create an algorithm to do so (e.g. AlphaTensor), it may be possible to improve training speed and/or inference with highly parallelized bitwise operations or analog arithmetic.
In the end, it may not even be necessary to prove P ?≠ NP. If we could find a clever way to apply our existing knowledge of approximation methods and pair this with highly specialized hardware then we may be able to solve many of the large, unruly, optimization problems we encounter in industry; ideally cheaper than the services widely available today.