The P versus NP problem is a major unsolved question in computer science. It asks whether every problem that can be quickly checked for a correct answer can also be quickly solved.

Here, "quickly" means an algorithm exists that completes the task in polynomial time. Polynomial time means the time needed to solve the problem grows in a predictable way as the problem becomes larger, unlike exponential time, where the time grows extremely fast as the problem becomes larger. Problems that can be solved in polynomial time belong to a group called "P." Some problems do not have known fast solutions, but if someone provides an answer, it can be checked quickly. These problems belong to a group called "NP," which stands for "nondeterministic polynomial time."

Answering the P versus NP question would determine if problems that can be checked quickly can also be solved quickly. If P is not equal to NP, which is widely believed to be true, it would mean some problems in NP are harder to solve than to check. These problems could not be solved in polynomial time, but their answers could still be checked quickly.

This problem is considered one of the most important unsolved questions in computer science. A solution would have major effects on mathematics, cryptography, algorithm development, artificial intelligence, game theory, multimedia processing, philosophy, economics, and other areas. It is one of the seven Millennium Prize Problems chosen by the Clay Mathematics Institute. Each problem offers a prize of $1,000,000 for the first correct solution.

Example

Think about this yes/no question: If you are given a partially filled Sudoku grid that is n squared by n squared in size, can you find at least one way to complete the grid so that every row, column, and n by n section contains all the numbers from 1 to n squared? It is easy to check if a proposed solution is correct for this type of Sudoku puzzle. However, no one knows if there is a fast method that can always answer "yes" or "no" for any such puzzle. This means the generalized Sudoku problem is in NP (solutions can be quickly checked), but it is unclear if it is also in P (solutions can be quickly found). It is important to study the generalized version of Sudoku because fixed-size Sudoku puzzles (like the standard 9×9 grid) have a limited number of possible grids. For these fixed sizes, the problem is in P because the answer can be found by looking up a list of all possible solutions.

History

The P versus NP problem was first clearly described in 1971 by Stephen Cook in his important paper titled "The complexity of theorem proving procedures." Leonid Levin independently introduced the same problem in 1973.

Although the P versus NP problem was formally defined in 1971, earlier ideas about related challenges existed. In 1955, mathematician John Nash wrote to the National Security Agency, suggesting that the time needed to break a complex code might grow very quickly as the key length increased. If this were true (though Nash doubted it), it would support the idea now called P ≠ NP, because checking a possible key can be done in a time that grows polynomially. In 1956, Kurt Gödel wrote to John von Neumann, asking if theorem-proving (now known to be co-NP-complete) could be solved in quadratic or linear time. He also suggested that if this were possible, then finding mathematical proofs could be automated.

Context

Computational complexity theory is the part of computer science that studies how much time or memory a computer needs to solve a problem. Time refers to how many steps it takes to solve a problem, and space refers to how much memory is needed.

To analyze these problems, scientists use a model of a computer. This model usually assumes the computer is deterministic, meaning it follows only one path at a time, and sequential, meaning it performs tasks one after another.

In this theory, the class P includes all decision problems (questions with yes or no answers) that can be solved quickly on a deterministic computer. The class NP includes all decision problems where a correct answer can be checked quickly if you have the right information, or solved quickly on a non-deterministic computer (a machine that can explore many possibilities at once). It is clear that all problems in P are also in NP.

A major question in computer science is whether P equals NP or not. Since 2001, William Gasarch has asked researchers about this. In 2001, 61% of 100 people believed P ≠ NP. In 2011, 83% of 151 people believed this, and in 2018, 88% of 124 people believed it. Among experts in 2018, 99% believed P ≠ NP. These surveys show opinions about this question but do not prove whether P equals NP or not. Gasarch explained that these polls reflect what experts think now but do not help solve the question directly.

NP-completeness

To understand the P = NP question, the idea of NP-completeness is helpful. NP-complete problems are problems that any other NP problem can be converted into in polynomial time, and their solutions can still be checked in polynomial time. This means that any NP problem can be transformed into any NP-complete problem. In simple terms, an NP-complete problem is an NP problem that is at least as difficult as any other problem in NP.

NP-hard problems are problems that are at least as difficult as NP problems. This means that all NP problems can be converted into NP-hard problems in polynomial time. However, NP-hard problems do not need to be in NP, which means they might not have solutions that can be checked in polynomial time.

For example, the Boolean satisfiability problem is NP-complete, as shown by the Cook–Levin theorem. This means that any problem in NP can be converted into a Boolean satisfiability problem in polynomial time. The Boolean satisfiability problem is one of many NP-complete problems. If any NP-complete problem can be solved in polynomial time, then P = NP. However, many important problems are NP-complete, and no efficient solution for any of them is known.

It may seem surprising that NP-complete problems exist, but one example is: given a Turing machine that stops in polynomial time, does a polynomial-size input exist that the machine will accept? This problem is in NP because, given an input, it is easy to check if the machine accepts it by simulating the machine. It is NP-complete because the verifier for any NP problem can be encoded as a polynomial-time Turing machine. Whether the problem has a solution depends on whether a valid input exists.

The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also called SAT. This proof, known as the Cook–Levin theorem, includes technical details about Turing machines and the definition of NP. After SAT was proven to be NP-complete, other problems were shown to be NP-complete using reductions. For example, Sudoku is an NP-complete problem. If Sudoku could be solved in polynomial time, it could also be used to solve Latin squares in polynomial time. This, in turn, could solve problems involving tri-partite graphs and 3-SAT, which is a special case of SAT. A polynomial-time solution to Sudoku would lead to a polynomial-time solution for SAT, which could then solve any other NP problem in polynomial time. Through such reductions, many seemingly unrelated problems are connected and can be transformed into one another, making them "the same problem" in a way.

Harder problems

Although it is not known whether P equals NP, problems outside of P are known to exist. Just as the class P includes problems that can be solved in polynomial time, the class EXPTIME includes problems that require exponential time. This means that any problem in EXPTIME can be solved by a deterministic Turing machine in time that grows exponentially with the size of the input. A problem is EXPTIME-complete if it is in EXPTIME, and all other EXPTIME problems can be transformed into it in polynomial time. Many problems are known to be EXPTIME-complete. Because it is proven that P does not equal EXPTIME, these problems cannot be solved in polynomial time. According to the time hierarchy theorem, they also cannot be solved significantly faster than exponential time. Examples include finding the best strategy for chess positions on an N × N board and similar problems for other games.

Deciding whether a statement in Presburger arithmetic is true requires even more time. In 1974, Fischer and Rabin showed that any algorithm for this task must take at least 2^(2^cn) time for some constant c, where n is the length of the statement. This means the problem requires more than exponential time. Even more complex are undecidable problems, such as the halting problem. These problems cannot be completely solved by any algorithm because, for any algorithm, there is at least one input that causes the algorithm to fail—either by giving the wrong answer, not finishing, or running forever without an answer.

Other types of problems beyond decision problems exist. One such class, called #P, includes counting problems. While an NP problem asks, "Are there any solutions?" the corresponding #P problem asks, "How many solutions are there?" A #P problem must be at least as hard as its NP counterpart because knowing the number of solutions immediately reveals whether at least one exists. Surprisingly, some #P problems are linked to problems in P that are easy to solve. For these problems, determining if solutions exist is simple, but counting them is very difficult. Many of these problems are #P-complete, meaning they are among the hardest in #P. If a polynomial-time solution existed for any #P-complete problem, it would allow polynomial-time solutions for all other #P problems.

Problems in NP not known to be in P or NP-complete

In 1975, Richard E. Ladner proved that if P is not equal to NP, then some problems in NP are neither in P nor NP-complete. These problems are called NP-intermediate problems. Examples of such problems include the graph isomorphism problem, the discrete logarithm problem, and the integer factorization problem. These are some of the few problems in NP that are not known to be in P or to be NP-complete.

The graph isomorphism problem is the task of determining whether two finite graphs have the same structure. A major unsolved question in complexity theory is whether this problem is in P, NP-complete, or NP-intermediate. The answer is unknown, but it is believed that the problem is not NP-complete. If graph isomorphism were NP-complete, the polynomial time hierarchy would collapse to its second level. Since most scientists believe the polynomial time hierarchy does not collapse to any finite level, it is likely that graph isomorphism is not NP-complete. The best algorithm for this problem, developed by László Babai, runs in quasi-polynomial time.

The integer factorization problem is the task of finding the prime factors of a given integer. As a decision problem, it asks whether the input has a factor smaller than a given number, k. No efficient algorithm for this problem is known, and this fact is used in modern cryptographic systems like the RSA algorithm. The integer factorization problem is in NP and in co-NP (and also in UP and co-UP). If this problem were NP-complete, the polynomial time hierarchy would collapse to its first level (meaning NP would equal co-NP). The most efficient known algorithm for integer factorization is the general number field sieve, which takes expected time to factor an n-bit integer. The best known quantum algorithm for this problem, Shor's algorithm, runs in polynomial time, though this does not clarify the problem's position relative to non-quantum complexity classes.

Comparison of P with "easy" problems

The discussion so far has assumed that problems in P are easy to solve and problems not in P are hard to solve. This idea is called Cobham's thesis and is widely used in complexity theory. However, there are important exceptions to consider.

First, some problems in P may still be impractical to solve. A theoretical algorithm that runs in polynomial time might require extremely large numbers or exponents, making it too slow for real use. For example, determining whether a graph G contains a fixed graph H as a minor can be solved in O(n) time, where n is the number of vertices in G. However, the actual time needed depends on a constant that becomes extremely large as the size of H increases. This constant is so large that it makes the algorithm inefficient for practical purposes.

Even if a problem is NP-complete and P is not equal to NP, practical solutions may still exist. Many NP-complete problems, such as the knapsack problem, the traveling salesman problem, and the Boolean satisfiability problem, can be solved effectively for real-world cases. Algorithms for these problems often perform well in practice, even though their worst-case time complexity is high. For example, the simplex algorithm in linear programming works efficiently in most cases, despite having exponential time complexity in theory.

Finally, some types of computation do not fit the Turing machine model used to define P and NP. Examples include quantum computing and randomized algorithms, which operate differently and may not be fully described by traditional complexity classes.

Reasons to believe P ≠ NP or P = NP

Cook restates the problem in The P Versus NP Problem as asking, "Does P equal NP?" According to surveys, most computer scientists believe that P does not equal NP. A major reason for this belief is that, after many years of research, no one has found a fast, polynomial-time algorithm for any of over 3,000 important NP-complete problems (see List of NP-complete problems). These algorithms were sought even before the concept of NP-completeness was defined. For example, Karp's 21 NP-complete problems, among the first identified, were already well-known problems at the time they were shown to be NP-complete. Additionally, if P equaled NP, it would lead to other surprising results that are currently considered false, such as NP equaling co-NP and P equaling PH.

It is also argued that problems which are hard to solve but easy to check for correctness reflect real-world experiences.

If P equaled NP, the world would be very different from what is typically assumed. There would be no special value in "creative leaps," and no major difference between solving a problem and recognizing its solution once found.

— Scott Aaronson, UT Austin

Some researchers, however, suggest that believing P does not equal NP might be overly confident and that exploring proofs for P equals NP should also be considered. For example, in 2002, the following statements were made:

The main reason given for believing P does not equal NP is the lack of progress in finding fast algorithms for exhaustive search. In my view, this is a weak argument. The space of possible algorithms is very large, and research is only just beginning. The solution to Fermat's Last Theorem also shows that simple questions may require very complex theories to answer.

— Moshe Y. Vardi, Rice University

Being attached to a single idea can hinder research planning. Both sides of every problem should be explored. Prejudice has caused famous mathematicians to fail in solving problems that had solutions opposite to their expectations, even when they had the tools needed.

— Anil Nerode, Cornell University

When replacing "polynomial time" with "linear time on a multitape Turing machine" in the definitions of P and NP, the classes DLIN and NLIN are formed. It is known that DLIN does not equal NLIN.

Consequences of solution

The problem receives much attention because the possible answers could have major effects. Solving it in either direction could greatly advance scientific understanding and might also lead to important real-world applications.

If it were proven that P equals NP, this could lead to powerful new methods for solving difficult problems. Many important problems in various fields are linked to NP-complete problems, so solving them efficiently could have both helpful and harmful effects. However, it is also possible that such a proof would not lead to practical solutions. The problem does not require specific details about the efficiency of the solution. A proof might only show that a solution exists without explaining how to find it. Even if the proof provides a method, if the method is too slow in practice, it might only interest scientists studying theory, but it could still encourage research into better solutions.

If P equals NP were proven, it could greatly affect cryptography, which depends on certain problems being hard to solve. A practical solution to an NP-complete problem, like 3-SAT, would break many current encryption systems. These systems would need to be changed or replaced with methods that do not rely on the assumption that P is not equal to NP.

Many problems that are currently very hard to solve, such as some in operations research and biology, are NP-complete. Finding efficient solutions to these problems could improve areas like logistics and medical research. In mathematics, solving NP-complete problems efficiently could lead to major changes. Kurt Gödel suggested that if a machine could solve any problem quickly, it would change how mathematics is done.

If a proof showed that P equals NP and included a practical method, it could allow computers to find proofs for mathematical theorems quickly. This would change how mathematicians work, as many proofs take a long time to find. However, Donald Knuth believes that even if P equals NP is proven, the proof might not be useful in practice if it does not provide a clear method for solving problems.

Proving that P does not equal NP would not offer practical benefits like solving problems quickly, but it would be a major step in understanding computational limits. It would show that many problems cannot be solved efficiently, guiding researchers to focus on other approaches. Much of this focus has already happened due to the belief that P does not equal NP.

Even if P does not equal NP, the average difficulty of solving problems in NP is still unclear. For example, some problems might be hard in the worst case but easy on average. Researchers have proposed different scenarios for how these problems might behave. A 2009 study at Princeton University explored these possibilities.

Results about difficulty of proof

The P = NP problem is still unsolved, even though many researchers have studied it and a large prize is offered for solving it. Trying to solve the problem has helped create new methods. Much of the useful research related to the P = NP problem has focused on showing that current proof methods are not enough to answer the question. This suggests that new methods are needed.

Most known proof methods in computational complexity theory fall into certain categories, and none are strong enough to prove that P ≠ NP. These challenges explain why NP-complete problems are important: if a fast solution method could be found for an NP-complete problem, it would solve the P = NP problem in a way that is not blocked by these barriers.

These challenges have led some scientists to think the P versus NP problem might not be solvable using standard math rules, like those in ZFC. This would mean that either P ≠ NP but cannot be proven using these rules, or P = NP but no proof exists showing that fast solutions are correct. However, if the problem is undecidable even with weaker math rules, then nearly fast solutions might exist for all NP problems. Assuming, as most experts do, that some NP problems lack efficient solutions, proving that the problem is unsolvable using these rules is impossible. This also means proving the problem’s independence from basic math rules like PA or ZFC is just as hard as proving all NP problems have efficient solutions.

Logical characterizations

The P = NP problem can be understood by examining how certain types of logical statements are described, based on research in descriptive complexity.

Consider all languages that describe finite structures with a specific set of rules, including a way to order elements. For languages in P, these can be described using first-order logic, which is a system for expressing relationships between objects, along with a tool called a least fixed-point combinator. This tool helps define rules that repeat or build upon themselves. Recursive functions, which are processes that repeat steps, can be created using this tool and the order rule. However, this description only works if the set of rules includes at least one additional element, such as a predicate or function, beyond the order rule. This ensures the amount of space needed to store these structures grows in a predictable way, proportional to the number of elements involved. This precise relationship defines the class P.

For NP, the languages described are those that can be expressed using a type of logic called existential second-order logic. This system allows statements that include "there exists" but not "for all" when referring to relationships, functions, or groups. The entire polynomial hierarchy, PH, includes all languages described by second-order logic, which includes both "there exists" and "for all" statements. This means the question "Is P a proper subset of NP?" can be rephrased as "Can existential second-order logic describe languages (of finite structures with a clear order and additional rules) that first-order logic with a least fixed-point combinator cannot?"

The word "existential" can be omitted in this description because P = NP is equivalent to P = PH. This is because if P equals NP, then NP would also equal co-NP, which would mean the entire polynomial hierarchy collapses to NP.

Polynomial-time algorithms

No known method for solving NP-complete problems works in polynomial time. However, some methods exist that could solve NP-complete problems in polynomial time if P equals NP. These methods work quickly for inputs that have a "yes" answer but may take too long for inputs with a "no" answer, making them impractical. One such method, created by Levin, is an example. It correctly solves the NP-complete problem called SUBSET-SUM. This method works in polynomial time only if P equals NP. "Accepting" means it gives "yes" answers quickly but may not finish when the answer is "no." Even if P equals NP, this method is not practical because it tries many other solutions before finding the correct one. If the shortest solution to solve SUBSET-SUM in polynomial time is b bits long, this method will test at least 2^b – 1 other solutions first.

Formal definitions

A decision problem is a question that takes a string of characters (from a specific set of symbols) as input and answers "yes" or "no." If there is a method (like a computer program or a theoretical machine called a Turing machine) that can correctly answer any input of length n in at most c times n steps, where c is a fixed number, then the problem is said to be solvable in polynomial time. These problems are grouped into a class called P. Formally, P includes all problems that can be solved by a deterministic Turing machine that runs in polynomial time.

A deterministic polynomial-time Turing machine is a machine that follows a single, clear path of steps and completes its task in a number of steps that grows with the size of the input but not too quickly.

The class NP includes problems that can be solved using a different kind of machine called a nondeterministic Turing machine (a traditional definition). A modern way to describe NP involves certificates and verifiers. Formally, NP includes all problems that have a specific rule for checking solutions quickly. A verifier is a method that checks whether a proposed solution is correct.

Let L be a set of strings using symbols from a specific set, Σ.

The set L belongs to NP if there exists a rule R that connects pairs of strings and a number k such that two conditions are met:
1. For every string x in L, there is a string y that, when combined with x using R, confirms x is in L.
2. A Turing machine that checks whether x and y satisfy R can do so in polynomial time.

A verifier is the Turing machine that checks R. A string y that confirms x is in L is called a certificate. Not all verifiers must work quickly, but for L to be in NP, at least one verifier must operate in polynomial time.

Determining whether a number is composite (not prime) is the same as checking if it belongs to the set COMPOSITE. It can be shown that COMPOSITE is in NP by confirming it meets the above definition (if numbers are represented in binary).

The set COMPOSITE is also in P, which means it can be solved quickly. This was proven with the discovery of the AKS primality test, a method that efficiently checks if a number is prime or composite.

There are many ways to describe NP-completeness.

Let L be a set of strings using symbols from a specific set, Σ.

The set L is NP-complete if it meets two conditions:
1. L is in NP.
2. Every problem in NP can be transformed into L in polynomial time.

Alternatively, if L is in NP and another NP-complete problem can be transformed into L in polynomial time, then L is NP-complete. This is a common method for proving that a new problem is NP-complete.

Claimed solutions

The P versus NP problem remains unsolved, but many people, including some professionals, have claimed to have found solutions. Gerhard J. Woeginger created a list of 116 claimed proofs between 1986 and 2016. Of these, 61 claimed that P equals NP, 49 claimed that P does not equal NP, and 6 proved other results, such as the possibility that the problem is undecidable. Some efforts to solve the P versus NP problem received short media coverage, but these claims were later shown to be incorrect.

Popular culture

The film Travelling Salesman, directed by Timothy Lanzone, tells the story of four mathematicians who are hired by the US government to solve the P versus NP problem.

In the sixth episode of The Simpsons seventh season, titled "Treehouse of Horror VI," the equation P = NP appears shortly after Homer accidentally enters the "third dimension."

In the second episode of season 2 of Elementary, called "Solve for X," Holmes and Watson investigate the murders of mathematicians who were trying to solve the P versus NP problem.