P vs NP: 50 Years On | Field Notes

But as of September 2020, the seven largest companies by market capitalization were Apple, Microsoft, Amazon, Alphabet (Google), Alibaba, Facebook, and Tencent, all of them roughly neck and neck with one another. It is not only the transformations among the giant corporations that are striking; the demand for computer talent is equally remarkable. According to statistics, the number of computer science graduates in the United States more than tripled between 2009 and 2020, yet this still falls short of the market's demand for talent in the field. The P versus NP problem has been a longstanding open problem for both mathematics and computer science, and it is listed as one of the Millennium Prize Problems of the Clay Mathematics Institute. Moreover, that organization has posted a bounty of over a million dollars for any researchers who can crack the problem. Near the end of this article I will use a number of examples to explain the P and NP problem. While that may not give us any deeper essential understanding of the problem, it does show how much of the thinking and the results around P and NP have driven research and progress in this field.

The P versus NP problem Suppose someone asked you: could you find, somewhere on Weibo, a group of people — roughly 300 of them in all — who are all friends with one another? How would you go about answering a question like that? Suppose you worked for a social networking company and had access to the entire platform's database — that is, you could see everyone's friend list. You could then try to enumerate every group of 300 people and check them one by one to see whether they all share the same circle of contacts; if they do, they form a clique. But the computational cost of such an algorithm is far too large, and there are simply too many such groups, so exhaustive enumeration of them all is generally out of the question. You could also try to be a bit cleverer about it: instead, start from a small group and then gradually grow that group by folding in people who are friends with everyone already in it. Of course, that may be difficult to carry out in practice. In fact, in theory this problem has no best-known solution at all, and nobody knows for sure whether any solution better than checking the groups one by one even exists. This example is in fact a typical instance of the P versus NP problem. NP stands for the class of problems whose solutions can be verified efficiently. For instance, if you already know that a particular set of 300 people might form a clique, you can quickly check whether all 44,850 pairs among them really are mutual friends. The clique problem is an NP problem. P, on the other hand, stands for the class of problems whose solutions can be found efficiently. We do not yet know whether the problem of finding such a group of 300 people also has the efficient-solvability property of P. In fact — surprisingly — the clique problem turns out to have the property of being "NP-complete." That is, we can solve the clique problem quickly and efficiently if and only if P = NP. A great many other problems are NP-complete as well, such as the 3-coloring problem (whether a map can be colored using only three colors so that no two adjacent regions share the same color), the traveling salesman problem (finding the shortest route through a list of cities so that the traveler returns to the starting city after having visited every city on the list), and many others besides. Formally, P stands for "deterministic polynomial time" — the class of problems that can be solved within a time limit that is polynomial in the length of the input. NP stands for "nondeterministic polynomial time." In the practical business of algorithm development, it is often better to view P and NP from another angle: we can treat the former as efficiently computable and the latter as efficiently checkable. If you would like to learn more about P and NP, you might read the 2009 survey article, or explore any of a number of popular-science books on the subject on your own. There are also somewhat more formal introductions, such as the book published by Michael Garey and David Johnson in 1979 — a book that no reader wishing to understand NP-completeness should miss: Garey, M. and Johnson, D. Computers and Intractability. A Guide to the Theory of NP-Completeness.W.H. Freeman and Company, New York, (1979). P vs. NP at 50 Years: AI Is Solving the Unsolved

Why discuss the P versus NP problem On that Tuesday afternoon in 1971, when Cook presented his paper on NP-completeness at the ACM Symposium on Theory of Computing, he proved that the satisfiability problem is NP-complete, while the tautology problem is NP-hard. The paper also conjectured that Tautology is a problem that does not have the property P — though at the time this was not rigorously proved. Either way, that paper and the methods of proof it introduced marked a major breakthrough in the theory of complexity. Proving a mathematical claim is usually a formidable challenge indeed. The foundational concepts of algorithms and proofs go back at least to ancient Greece, though of course the Greeks never considered questions like P and NP. The theoretical foundations of efficient computation and of nondeterminism, however, were only developed in the 1960s. But the P versus NP problem had been posed long before then — we simply had not yet given it a formal name. Back in 1956, Kurt Gödel wrote a letter to John von Neumann in which he sketched out the P versus NP problem. That letter was not discovered until 1988, after which it circulated very widely indeed. Richard Karp was the first person to bring the P versus NP problem to wide attention in the true sense; he introduced it in his 1972 paper, which soon drew very broad interest. We know that many famous combinatorial problems are NP-complete, including Clique, 3-coloring, and the traveling salesman problem. In 1973 Leonid Levin, then in Russia, published a new paper building on his own independent results obtained two years earlier, in which he formulated the P versus NP problem. By the time Levin's paper reached the West, P versus NP had already established itself as the single most important open problem in the theory of computation.

Optiland In a classic 1995 paper, Russell Impagliazzo described five different levels of possibility for the P versus NP problem — five possible worlds: Algorithmica: P = NP or something theoretically equivalent, e.g. fast probabilistic algorithms for NP Heuristica: NP problems are hard in the worst case, but on average they can still be solved in practice Pessiland: we can easily create hard NP problems — the worst of all the possibilities, because we can neither solve hard problems in an average-case sense nor extract any clear advantage from their hardness Minicrypt: problems of cryptographic one-way functions exist, but we still do not have public-key encryption Cryptomania: public-key cryptography — that is, two parties can exchange encrypted information over a public channel and then decrypt it with a public key These five levels have no formal definitions; they are informal categories shaped by people's understanding of P and NP. Even so, of the five, Cryptomania is widely regarded as the most likely to be the world we actually live in. Impagliazzo drew on a central, core idea in the theory of P and NP — the notion that "we cannot have everything." Perhaps we can solve hard NP problems, or perhaps we can crack the essential keys of cryptography — but we cannot conquer both of them at the same time. Still, perhaps we are slowly heading toward a de facto Optiland: great strides in machine learning, as well as in hardware and software optimization, let us solve, to a considerable degree, problems that were once thought entirely inconceivable — speech recognition, protein folding, and more. For the most part, though, our cryptographic protocols remain secure, so there is no need to worry too much about it. In my 2009 survey, in the chapter titled "What If P = NP?", I argued that if we applied Occam's razor then learning would become easy — we would only need to find the smallest program consistent with the data, which is the very core of the problem. At that point, tasks once considered extremely difficult to crack — visual recognition, speech recognition, translation, and any number of others — would become trivial. We would also make far better predictions, understanding, and models of weather, earthquakes, and other natural phenomena. Today we unlock our phones with facial recognition, hold voice conversations with smart devices to ask questions and get satisfying answers in return, and translate spoken words or typed text into other languages. Our phones alert us about the weather and other breaking events, with forecasts far better than anything we were able to manage a decade or so ago. Meanwhile, apart from brute-force-style attacks against short key lengths, our cryptography is still essentially robust and secure. So now, let us look at how recent progress in computation, optimization, and learning is carrying us — perhaps — toward Optiland!

Solving hard problems In 2016 Bill Cook and his colleagues set themselves a challenge: to work out how to visit every pub in Britain along the shortest possible route. They listed the 24,727 known pubs and then actually set out on foot to visit them all. The resulting walk covered 45,495,239 meters — about 28,269 miles — which is farther than a trip right around the globe. Cook actually cheated a little here: he did not walk to every single pub, quietly skipping some in order to keep the trek from being quite so absurd. When the story was publicized in the British media, many readers left comments saying: "You didn't come to the pub next to my house!" So Cook and his company went back to the drawing board, expanding the pub list to 49,687 and bringing the total journey to a staggering 63,739,687 meters — 39,606 miles. Yet compared with the first trip, this new pub crawl required only 40% more walking to cover more than twice as many pubs. P vs. NP at 50 Years: AI Is Solving the Unsolved An overview map of the route traversing all 49,687 pubs in Britain A pub-crawling tour of this kind is in effect a variant of the traveling salesman problem, one of the most famous NP-complete problems. The number of possible tours through all 49,687 pubs is on the order of a 3 followed by 211,761 zeros. Cook's computer, of course, did not search the entire set; instead it used a variety of different optimization techniques. More impressive still, the tour came with a proof of optimality based on the duality of linear programming. Beyond the traveling salesman problem, we have also seen major advances in solving satisfiability and mixed-integer programming — a variant of linear programming in which some of the variables are required to take integer values. With high-quality heuristics assisted by fast processors, specialized hardware systems, and distributed cloud computing, practitioners can routinely solve real-world problems containing tens of thousands of variables and millions of constraints. Faced with an NP problem, one can typically formulate it as a satisfiability or mixed-integer programming instance and hand it over to the best available solver, letting the raw power of the computer find the answer automatically. These tools have already been applied successfully to the verification of circuits and code, automated testing, computational biology, system security, product and packaging design, financial trading, and even the solution of difficult mathematical problems.

Data science and machine learning It is hard to ignore the revolutionary impact that machine learning has had in recent years — neural networks in particular. The conceptual basis of artificial neural networks is essentially the computation of weighted threshold functions — an idea that originated in the 1940s with the work of Warren Mcculloch and Walter Pitts. In the 1990s Yoshua Bengio, Geoffrey Hinton, and Yann Lecun developed the backpropagation algorithm to deepen layered neural networks, achieving results of extraordinary quality. At the same time, breakthroughs in computer hardware — in computation and storage — brought faster, more distributed computing units, specialized hardware, and vast quantities of data, all of which together helped machine learning accomplish a great many functions that resemble human ones. The ACM recognized the contributions of Bengio, Hinton, and LeCun and awarded them the Turing Award in 2018. Some readers may well ask: how does machine learning connect to the P and NP problems? Occam's razor says: entities should not be multiplied beyond necessity. If P = NP, we could use this idea to create powerful learning algorithms — find the smallest circuit consistent with the data. Even if P ≠ NP, machine learning can learn and approximate this idea, and that is what gives it its power. Even so, a neural network may not be a truly "minimal" circuit, though perhaps it is about as small as we can manage. The deep learning methods we use today typically have fixed architectures; the only things that vary are the weights on the connections between neurons. To achieve enough expressive power to generalize, these networks usually carry hundreds or thousands of weights. That limits what deep networks can do — in other words, they are not simple enough. They can do very well at tasks such as face recognition, but they cannot learn multiplication from examples. Universal distributions and GPT-3

Consider the setting of distributions over the infinite set of binary strings. We cannot have a uniform distribution, but we can create one in which all strings of the same length have the same probability. Still, some strings matter more than others: the first million digits of π, for example, are far more meaningful than a million randomly generated digits. We might want to assign higher probability to the more meaningful strings, and today we have a great many ways to do exactly that. Indeed, a universal distribution has already been found that approximates any other computable distribution — and this distribution has deep connections to learning. For example, any algorithm that can learn this distribution with a small error rate will be able to learn every computable distribution. The catch is that even if P = NP, such a distribution is in general uncomputable anyway. If P = NP, we could still gain something useful by creating a distribution that is universal for the other efficiently computable distributions. So what can we get out of machine learning? Consider the Generative Pretrained Transformer (GPT). GPT-3 was released in May 2020, carrying 175 billion parameters and trained on 410 billion tokens. These tokens come from a wide range of text corpora. It can answer questions, write text from a prompt, and even perform some basic coding work. There is still a long way to go, but GPT-3 has been widely praised for the naturalness of what it generates. In a sense, we can view GPT-3 as a special kind of distributional method. Inside it we can look at the probability that an algorithm generates a given output — a weakened version of a universal distribution. If we restrict a universal distribution to a given prefix, it provides random samples conditioned on that prefix. GPT-3 can likewise build on such prompts, handling a very wide range of domain knowledge with no further training whatsoever. As this line of research continues, we move closer to a general benchmark with built-in learning: sampling a random example from a given context. Science and medicine

In science, we build understanding by carrying out large-scale simulations. In exploring the course of nuclear fusion reactions, for example, researchers have already obtained some very good results. They can apply a formal methodology: posit a hypothesis about a physical system, then work with that hypothesis over and over again to run reactions and simulations. If our results disagree with reality, the model is discarded and we start over. Once we have a strong model, we can run inside a physical simulation system the many tests that would be far too expensive to run in real experiments. If P = NP, we could use Occam's razor to create hypotheses — find the smallest circuit consistent with the data. Machine learning techniques can follow precisely this path to automate the whole process of hypothesis creation. Once we are given data, whether obtained through simulation or real experiments, machine learning can create models that fit the data for an optimal match. We can use these models to make predictions and then test them, just as before. Although these techniques let us surface hypotheses and models we might otherwise miss, they can also produce false alarms. Humans tend to be satisfied with a hypothesis at 95% confidence (which means that only one bad hypothesis in twenty gets through). Machine learning and data science tools let us generate hypotheses at scale, and every one of them carries the risk of drifting away from reality. That limits where they can safely be used: medical practitioners, for instance, cannot afford to take such risks, since these problems in a diagnosis would land them in very deep trouble indeed. Biological systems are extraordinarily complex structures as well. We know that human DNA forms a sophisticated code describing how our bodies are built and what functions they perform. Sadly, we still know very little about how it works. On November 30, 2020, Google's DeepMind released AlphaFold, a new algorithm that predicts the shape and structure of proteins from their amino acid sequences. AlphaFold's predictions nearly matched the accuracy of actually building an amino acid sequence in the lab and measuring the resulting protein's shape. There is still some controversy over whether DeepMind truly "solved" the protein folding problem, and it is too early to assess its impact — but in the long run this can give us a new digital tool for studying proteins, for understanding how they interact, and for learning how to design DNA to fight disease. Thinking beyond P and NP: chess

NP is like a maze, a matter of carrying out all manner of operations on a board of arbitrary size. Sudoku is likewise an NP-complete problem: it asks you to solve for a given set of numbers placed in some of the squares. But when we ask who wins from a given initial position, are we simply unable to give an accurate answer? Even granting P = NP, it would not necessarily hand us a perfect chess program to solve the problem — we would need a program that guarantees White plays this move, forcing Black to play that one, then White follows the plan with the next move, forcing Black..., until finally White wins. P = NP alone cannot carry out all of those alternating White and Black moves. Games like this are often called PSPACE-hard — hard either to compute or to solve using a reasonable amount of memory within an agreed amount of time. Depending on the exact limits imposed by the rules, chess and Go may be even harder. This does not mean that, if P = NP, you could not get a good chess program. In fact, to some extent, the larger a chess program is, the smarter it tends to be. We can find an efficient computer program that beats every other program of somewhat smaller size. Meanwhile, even without P = NP, computers have become extraordinarily strong both at chess and at Go: in 1997 IBM's Deep Blue defeated the reigning world chess champion. Besides, machine learning has brought tremendous progress to computer games. Consider the celebrated AlphaZero, an AI program developed by DeepMind in 2017. AlphaZero uses a technique called Monte Carlo tree search (MCTS), in which the two players make random moves to determine the best course of action. AlphaZero uses deep learning to predict the best distribution over game positions, optimizing its chances of winning with MCTS. Although AlphaZero was not the first work to use MCTS, it has no built-in artificial strategy and uses no existing game database. AlphaZero learns only the rules of the game. That is what lets AlphaZero shine in both chess and Go — two games that, apart from alternating moves and a fixed-size board, have nothing in common in their rules or objectives. DeepMind has recently made new moves with MuZero. It does not even receive the full rules of the game, only some representation of the board position, a list of legal moves, and some understanding of which positions are won or lost. In other words, we have now reached a stage at which pure machine learning can comfortably defeat most humans and most heuristic algorithms in highly complex problems such as chess and Go. Human prior knowledge only gets in the way and ruins the effort. For games like chess and Go, machine learning can succeed even when P = NP does not hold. Incredible. Interpretable artificial intelligence

Many machine learning algorithms already seem to achieve very good results, yet we do not know why. If we look closely at the internal parameters of a neural network for speech translation or image recognition, it is hard to understand why it takes that particular action or processes things that way. One might well ask: as long as it has the ability, why should we care about any of this? Here are several reasons: trust, fairness, security, causality. Trust: Just how do we know whether a neural network is functioning properly? Apart from examining inputs and outputs, we cannot analyze or understand the other intermediate variables. Different applications carry different levels of trust. If Netflix recommends a bad movie, no great harm is done — but if a self-driving car recommends a turn that drives the car into a wall, things get very serious indeed. Fairness: A great many applications learn from a training set, and the data in that set may not be entirely fair or free of bias. If we do not understand the program, we may be unable to correct its biases and discrimination. Racial discrimination is a serious matter, after all. Security: If we use machine learning to monitor data-security systems or even physical security systems, an uninterpretable machine learning model may be unable to tell you what its vulnerabilities are — especially when our adversaries are adaptive. If we can understand the code and the structure of the network, we can discover and patch these security holes. Of course, if our enemies have the code, they too may discover the vulnerabilities and mount attacks against our organization. Causality: For the moment, at best we can check whether a machine learning algorithm is correlated only with the kinds of output we want. But understanding the code can help us understand the causal relationships in the data, leading to better scientific theories and medical results. Would P = NP give us better computer programs? If you had a fast algorithm for solving NP-complete problems, you could use it to find the shortest route matching the traveling salesman problem — but you would not know why the method works. On the other hand, we all hope to obtain interpretable algorithms, because they give us real insight into their properties. In the research community we are studying interpretable artificial intelligence, at conferences such as ACM Fairness Accountability and Trust. Limitations of machine learning Although machine learning has made remarkable progress over the past few decades, these systems are far from perfect. In most applications they are still trounced by humans. We will keep improving machine learning through new and better-optimized algorithms, by collecting yet more data, and by developing ever faster hardware. Even so, machine learning does seem to have quite a few limitations of its own. As we saw above, machine learning brings us ever closer and closer to P = NP, yet we never quite reach it. In breaking ciphers, for example, progress has been slow; we will discuss this later. Machine learning likewise seems unable to learn simple arithmetic relationships — summarizing patterns across large numbers of digits, say, or multiplying large numbers. One can imagine that combining machine learning with symbolic mathematical tools would surely work very well. Although we have already seen some progress in applications to theorem proving, we remain far from the functionality we dream of. I am writing a related paper myself. Likewise, P = NP would make these tasks easier, or at least more tractable. Machine learning typically performs poorly on samples drawn from a distribution different from its training data. This may stem from low-probability edge cases — for example, when the training data does not adequately include all ethnic groups, recognition of people from certain countries or races is poor. Deep neural network algorithms may have millions of parameters, and so they may fail to achieve good generalization across distributions. If P = NP, one could generate a model of minimal size that makes the very best generalization — but unless we can run the experiment, we will never know whether this is a P versus NP problem. As with machine learning, none of our current work comes anywhere close to artificial general intelligence in the true sense. This artificial general intelligence means an artificial system with genuine understanding of a subject, or genuine consciousness or self-awareness. Defining these terms can be tricky, and it is somewhat controversial too. Personally, I have not yet seen a reasonable formal definition of artificial general intelligence; I have simply latched onto a perceptual understanding of the concept and put it into words. I suspect we will never achieve true artificial general intelligence, even if P = NP.

Cryptography Although we have made great progress on NP problems, much of cryptography has barely budged. That includes the many forms of encryption built on one-way functions, secure hashes, public-key cryptography, and more. An efficient NP algorithm could in fact break every cryptosystem there is, except those that are information-theoretically secure (such as one-time pads and some quantum-physical secure systems). We have already seen many successful attacks on network security, but they usually stem from poor server configuration, bad random-number generators, or plain human error — almost never from a problem with cryptography itself. Most CPU chips today have encryption built in, so once we use public-key cryptography to set up a private key, we can send encrypted data as easily as if we were sending plaintext. Encryption provides the underlying technology for blockchain and cryptocurrencies, which means people trust the technology enough to exchange cash for Bitcoin. Research by Michael Kearns and Lesilie Valiant in 1994 showed that learning the smallest circuit — even learning the smallest bounded-depth neural network — can be used to factor integers and break public-key cryptosystems. So far, however, machine learning has not yet succeeded in breaking cryptographic protocols. One might well ask: since we have made so much progress on so many other NP problems, why is cryptography the one area that fails to yield? In cryptography we get to choose the problem and design methods purpose-built for this scenario, so we achieve good results. Other NP problems are usually handled by generic methods formed by the programs themselves. These automatically matched methods are not tailored to the task at hand, so they are neither the most suitable nor the hardest way to go. Quantum computing is, as far as we know today, the only thing that threatens the security of the public-key protocols that underpin the internet. Shor's algorithm can be used to factor large integers and perform other related number-theoretic computations. This concern can be addressed in several ways. Although quantum computing has made astonishing progress, it remains a long way from breaking today's cryptosystems, since it still cannot process enough entangled bits. Some estimates suggest that it may take decades or even centuries before Shor's algorithm running on a quantum computer genuinely threatens the public keys in use today. Meanwhile, researchers have made good progress developing public-key cryptosystems resistant to quantum attack. We will discuss quantum computing in detail later in this article. Factoring is not currently known to be an NP-complete problem, and even without large-scale quantum computers, a mathematical breakthrough could certainly yield highly efficient and useful solutions. Whatever we make of the future of quantum computing, a computer that has acquired several public-key systems might well solve the factoring problem.

Friction-like complexity Then again, when we are faced with so many hard-to-compute problems, what advantage do we actually gain from them — or what can we learn from the experience? I thought of cryptography. But if the Creator made certain computational problems extremely difficult and complex, even hard to solve and implement, there must be an inherent reason — much like the phenomenon of friction in nature. In the physical world, friction is usually something we must expend extra energy and work to overcome, yet without that ever-present resistance we could not even walk, run, or move forward. Likewise, in the world of computers, complexity may cause computational difficulty — but without it we might face even thornier problems, akin to being unable to move at all. In many cases, P = NP would do away with this friction altogether. Many recently published papers on the theory of computation tell us that eliminating friction-like computational complexity would produce a great many negative consequences. For example, if computational complexity were eliminated, people would no longer be able to reveal their thoughts: we would see only the actions others take and not the purposes behind them. Economists have a term for this — preference revelation — the attempt to infer the true underlying purpose from the behavior we exhibit. For a large part of the past, we simply lacked enough training data to support the training of such models, so this kind of program remained a castle in the air — a hopelessly imprecise "work of art" with no practical use whatsoever. Today, we collect enormous amounts of personal data from people's web search histories, photos and videos on their social accounts, purchase records on their game accounts, their browsing trails online, their footprints in the real world, and the privacy information left behind on all kinds of smart devices. Datasets are therefore already plentiful. At the same time, machine learning also has the capacity to process this complex information, so it can make very precise predictions and estimates on that basis. More often than not, computers know far more about us than we know about ourselves. Our technology today is already powerful enough to develop smart glasses that let you know, the instant you put them on, all manner of information about the person in front of you — name, age, height and weight, hobbies and interests, even political preferences. In other words, in the age of big data — because of machine learning and the abundance of private information — problems that were once extremely complex and almost impossible to carry out have been conquered by computers, and that has also brought privacy leaks: complexity can no longer protect our privacy for us. We need to protect individuals' privacy and security through law and through accountability constraints on corporations. The phenomenon of "friction" in the computer world extends beyond privacy. The U.S. government deregulated airline pricing in 1978, so if travelers wanted to find the cheapest route they had to make many phone calls to many airlines, or go through a travel agency. But travel agencies, of course, rarely work hard to find you the cheapest fare; they look for the route that earns them the most. The airlines have different philosophies for survival: some may strive to maintain high service quality and therefore charge a bit more, while others want to attract more passengers with low prices. Today we can easily use computer programs to find the cheapest airline fares, so airlines have gone to war over price, each hoping to compute the optimal pricing to improve its load factor — and in the process, service attitude and the passenger experience may well be sacrificed. The "friction" of computers, or complexity, also helps fight cheating. When I was a college student back in 1980, I was tortured by calculus problems every single day, doing all kinds of mathematical computations from morning to night, my life a living hell. But today those calculus problems are child's play before Mathematica and Matlab, cracked effortlessly with a single line of code. I am a teacher now, and in my courses I can no longer assign homework problems that cannot be found online for students to practice on. Even more absurdly, I can now use GPT-3 or its successor's optimized code to generate some of that homework myself. So when tools like GPT can already answer these very complex questions automatically, how do we motivate students, or keep them from cheating and slacking off? Stock trading is another area hit especially hard. In the past, stock trading usually took place inside a great big exchange, just as we see in the movies, where the traders there direct buying and selling with a very cool gesture and match the best price with a single glance. But nowadays algorithms automatically adapt to the best prices and buy and sell stocks for us — occasionally causing "flash crashes." Machine learning algorithms have grown very powerful: they can make certain decisions in place of humans, perform face recognition, match social media content to users, and even render certain judicial verdicts. All of these decision systems have brought convenience to people, but they have also created major social challenges. For instance, discrimination and political polarization are being widened. The problem is too complex for us to sum up in a single sentence. The problems described above are only a small part of such scenarios. As computer scientists, our aim is to make computation as efficient and simple as possible, but we must preserve the cost of reducing computational complexity — that is, computational "friction."

The power of quantum computers As Moore's law runs out, computer researchers have turned their attention to the field of quantum computers, and in recent years both research into and applications of quantum computing have been growing dramatically. Large technology companies such as Google, Microsoft, and IBM, as well as all manner of startups, are investing heavily in research on quantum computers. The United States has launched a national-level quantum computing research program, and other countries such as China are following suit one after another. In 2019 Google announced that it had achieved "quantum supremacy" using a quantum computer with 53 quantum bits, solving many computational tasks that today's classical computers simply cannot. Although many people have questioned this claim, we are undoubtedly at the dawn of a new era of quantum computing. Even so, we remain a long way from being able to run Peter Shor's quantum algorithm and from having a true quantum computer. Conservatively speaking, we still have tens of thousands of qubits to conquer. Generally speaking, a quantum computer can be understood as a system whose number of states is represented by ordinary bits — for example, the 2^53 states of a 53-qubit computer. This might suggest that we could solve NP-complete problems by creating a tremendously large number of state bits — in other words, brute force makes miracles. But unfortunately, we currently cannot prove that a quantum computer can fully manipulate these state bits; that is, we do not know what algorithm would solve NP-complete problems. From this angle, the problem already exceeds the limits of Grover's algorithm.

Complexity updates Since 2009 we have made a number of major advances in the theory of efficient computation. Although these results do not help us much in resolving P and NP directly, they may shed light on related questions from the side and inspire later research and development. Graph isomorphism Some NP problems cannot be characterized as belonging to P (efficiently solvable) or as being NP-complete (as hard as the Clique problem). The most famous example we discussed earlier, integer factoring, still requires exponential time to solve. For another problem of this very kind — the graph isomorphism problem — we have recently seen some genuinely dramatic progress. The graph isomorphism problem asks whether one can find a single common representation in which two graphs are completely identical. To give a concrete example, in Facebook terms: when we are given two groups of 1,000 people, can we map them onto another group in which the friendship relationships are unchanged? (Little A and Little B are friends; in the other group, A' and B' are also friends.) The graph isomorphism problem gained a number of theoretical results back in the 1980s. Also in the 1980s, someone used an interactive method to prove that graph isomorphism is not NP-complete, and that it is in fact not very difficult at all: in some practical situations, heuristic methods can quickly find a solution. Even so, we still have not been able to find an algorithm that quickly finds a solution in every setting. Laszlo Babai studied this problem in depth in 2016 and published a polynomial-time solution algorithm for graph isomorphism. To put it simply, a problem in P can be solved in polynomial time — that is, for some constant k the complexity is n^k, where n is the size of the input, such as the number of people in each group. A quasipolynomial-time algorithm runs in time n^(logn)k, only slightly worse than polynomial time, but at least far better than the 2^n^ε complexity we expect for NP-complete problems. Babai's proof combines combinatorics and group theory and is a truly excellent piece of work on every level. Although it is still some way from letting this algorithm run to completion in polynomial time, Babai has delivered an important theoretical result. This is a major advance in the gap between P and NP-complete problems. Circuit design If NP has no smallest circuit over the full basis of circuit design (that is, over AND, OR, and NOT gates), then no solution of P = NP can exist. Although in the golden age of circuit development in the 1980s there was no explicit proof disproving the hypothesis P = NP, the various surveys in 2009 likewise showed that circuit complexity had produced no major results over the previous twenty years. In 1987 Razborov and Smolensky proved that it is impossible to compute the majority function for certain fixed primes p with constant-depth circuits over AND, OR, NOT, and Mod_p gates. But for circuits that make use of Mod_6 gates, we can hardly prove this result at all. Even if we can prove that NEXP (the exponential-time version of NP) cannot be computed by small, constant-depth circuits over AND, OR, NOT, and Mod_6 gates, the question of whether P and NP are equal remains unanswered after decades. Then again, constant-depth circuits are theoretically regarded as having very weak computational power; we have made no substantive progress on them in all these years, and the fact that recent circuit algorithm results go unnoticed also confirms this phenomenon. In 2010 Rayan Williams showed that NEXP indeed does not have those constant-depth circuits that use Mod_6 or other Mod gates. In doing so he created a new technique that solves the problem using satisfiability algorithms. Under this algorithm's implementation, the lower bound is better than trying all possibilities or achieving a brute-force result with some complexity tools. Later, Williams and his student Cody Murray carried out further research, and the results show that a nondeterministic quasipolynomial-time solution exists for any fixed small constant-depth circuit without Mod_m gates. However, proving that NP has no small circuits of arbitrary depth still seems as remote as ever. Complexity strikes back? In that 2009 survey, I discussed a brand-new approach in geometric complexity theory, in a chapter called "A New Hope" — an approach built on the algebraic geometry and representation theory developed by Ketan Mulmuley and Milind Sohoni in order to tackle the P and NP problems. Briefly put, Mulmuley and Sohoni created a family of high-dimensional polytope spaces to find a mapping between P and NP in the algebraic version of NP, thereby reconstructing, understanding, and solving the problem within that space. In one of their conjectures, they hypothesize that such a polytope contains special properties of some representation-theoretic object. In 2016 Peter Burgisser, Christian Ikenmeyer, and Greta Panova demonstrated theoretically that such an approach is impossible. Although the research results of Burgisser, Ikenmeyer, and Panova refuted the GCT approach to separating P and NP, they did not refute this experimental method and line of thinking. One can still create different polytope spaces according to the number of such representation-theoretic objects. Even so, we cannot bet everything on the polytope approach solving the P and NP problems for us in the near future.

The possibility of the impossible When we step back and reflect on the P and NP problem, we can see that it carries many different meanings. The formal mathematical definitions of P and NP remain its official definitions — cold and clinical, perhaps, but the most complete in meaning. And whoever solves this mathematical problem also gets to collect a multimillion-dollar prize, right? Sometimes, although we can glimpse ways to solve P and NP through tools such as computability theory, circuits, proofs, and algebraic geometry, there is currently no powerful method that can completely resolve the P and NP problems. From this angle, we are abstracting the P and NP problems into various domains and lowering their difficulty — that is, moving ever further from the original problem. In real life, too, we have plenty of practical NP problems still awaiting a solution. In the classic 1976 book Computers and Intractability: A Guide to the Theory of NP-Completeness, Garey and Johnson give the example of an unlucky employee whose boss asks him to solve an NP-complete optimization problem. In the end, the unhappy employee goes to his boss in distress and says: I am truly stuck — I cannot find an efficient algorithm to solve this problem, and not only me, but neither Bill Gates nor Wozniak in this entire world can do anything about it. The book concludes that the boss should not fire this employee, because there is no one else who can solve the problem either. In the early days of P and NP, we treated NP-completeness as an obstacle: these were problems we simply could not solve. But with the development and steady progress of computers, we have found that by combining heuristics with brute-force computation we can make very good progress on a great many NP problems. In Garey and Johnson's story, if I were the boss I would probably not fire that unlucky employee; instead I would suggest he use some new methods, such as mixed-integer encoding, machine learning, and brute-force search to crack it. The idea that NP-complete means impossible has, in fact, already gone out of date; that era has become a thing of the past. NP-complete only means that there may be no algorithm that is always efficient and scalable — but the problem itself can still be solved. In my book on P and NP published in 2013, I have a chapter titled "Brave New World." In it I describe an idealized world in which a Czech mathematician proves P = NP, thereby providing a very efficient solving algorithm for all NP problems. Although we do not live in such an ideal world, and perhaps never will,, with advances in medicine and the rise of new concepts such as virtual worlds and the metaverse, the old and beautiful topic of P = NP no longer seems entirely out of reach. But then again, we are striding forward in directions that could very nearly overturn the very idea of the P = NP problem. Rather than forever treating it as an obstacle for algorithms, we might imagine the road to a solution for P and NP, explore some genuinely new directions within the problem, and uncover the possibility buried in the impossible.