- In full:
- polynomial versus nondeterministic polynomial problem
- Related Topics:
- computational complexity
- Millennium Problem
P versus NP problem
-
What is the P versus NP problem in mathematics?
The P versus NP problem, a pivotal question in computational complexity, asks whether all NP problems are also P problems. Problems that can be solved by an algorithm in polynomial time are P problems, and are considered tractable. NP problems have solutions that can be guessed and verified in polynomial time.
A problem is NP-hard if its solution can be used to solve any NP problem. Problems that are both NP and NP-hard are called NP-complete. It is unknown whether polynomial time algorithms exist for NP-complete problems. Discovering one would mean P = NP = NP-complete, revolutionizing computer science and mathematics.
Modern cryptography relies on the assumption that factoring large numbers is not in P. Finding a polynomial time algorithm for factoring would compromise many encryption methods. The P versus NP problem was also named a Millennium Problem by the Clay Mathematics Institute, with a \$1 million reward for its solution.
2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
What do the terms "P" and "NP" stand for?
In computational complexity theory, the terms "P" and "NP" refer to classes of problems based on how easily they can be solved by a computer.
- P (Polynomial time): This class includes problems that can be solved by an algorithm in polynomial time, meaning the number of steps required to find the solution is bounded by a polynomial function of the input size. These problems are considered tractable or easy to solve.
- NP (Nondeterministic Polynomial time): This class includes problems for which a solution can be guessed and verified in polynomial time. "Nondeterministic" means that no specific rule is followed to make the guess.
The P versus NP problem questions whether every problem whose solution can be quickly verified can also be solved quickly. In other words, it asks whether all NP problems are also P problems.
2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
What kind of problems belong to the group P?
In computational complexity, problems belonging to the group P (or P problems) are those that can be solved by an algorithm in polynomial time. This means the number of steps the algorithm takes to find a solution is limited by a polynomial function of n, where n represents the length of the input for the problem. Because they can be solved relatively quickly, P problems are considered "easy," or tractable.
An example of a problem that was shown to belong to P is linear programming. While it was initially thought to be in the category NP, Russian mathematician Leonid Khachian developed a polynomial time algorithm for it, which allowed formerly intractable problems to be solved.
2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
What kind of problems belong to the group NP?
NP problems are those for which a solution can be guessed and then verified in polynomial time, without following a specific rule to make the guess.
Many significant computer-science problems belong to this class, such as the traveling salesman problem, satisfiability problems, and graph-covering problems. Linear programming problems are NP. It is unknown whether efficient algorithms exist for NP-complete problems.
A problem is NP-complete if it is within NP and all other NP problems can be reduced to it in polynomial time. An efficient algorithm for any NP-complete problem implies that an efficient algorithm can be found for all NP problems.
2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
Why is it important to know if P equals NP or not?
Knowing whether P equals NP is a critical question in computer science and mathematics because it addresses the fundamental limits of computation.
If P = NP, every problem whose solution can be quickly verified could also be quickly solved. This would revolutionize fields like cryptography, optimization, and artificial intelligence, as it would provide efficient solutions to many currently intractable problems. For example, modern cryptography relies on the assumption that factoring large numbers is not in P. An efficient algorithm would break most modern encryption schemes.
Conversely, if P ≠ NP, it would confirm that some problems are inherently harder than others, requiring exponential time to solve. This would guide researchers to focus on approximation algorithms and heuristics for NP problems instead of searching for elusive polynomial-time solutions.
2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles. -
What are some real-life examples or consequences if P turns out to be equal to NP?
The P versus NP problem is a major question in computer science and mathematics about whether all NP problems are also P problems.
If P turns out to equal NP, it would mean that every problem whose solution can be quickly verified can also be quickly solved. Currently, modern cryptography relies on the assumption that factoring large numbers is not in P. Therefore, finding a P solution would break most modern encryption schemes.
2 Britannica SourcesCreated from Britannica articles using AI. AI can make mistakes, so verify using Britannica articles.
P versus NP problem, in computational complexity (a subfield of theoretical computer science and mathematics), the question of whether all so-called NP problems are actually P problems. A P problem is one that can be solved in “polynomial time,” which means that an algorithm exists for its solution such that the number of steps in the algorithm is bounded by a polynomial function of n, where n corresponds to the length of the input for the problem. Thus, P problems are said to be easy, or tractable. A problem is called NP if its solution can be guessed and verified in polynomial time, and nondeterministic means that no particular rule is followed to make the guess.
Linear programming problems are NP, as the number of steps in the simplex method, invented in 1947 by American mathematician George Dantzig, grows exponentially with the size of the input. However, in 1979 Russian mathematician Leonid Khachian discovered a polynomial time algorithm—i.e., the number of computational steps grows as a power of the number of variables, rather than exponentially—thereby showing that linear programming problems are actually P. This discovery allowed the solution of formerly intractable problems.
A problem is NP-hard if an algorithm for its solution can be modified to solve any NP problem—or any P problem, for that matter, as P problems are a subset of NP problems. (Not all NP-hard problems are members of the class of NP problems, however.) A problem that is both NP and NP-hard is said to be NP-complete. Thus, finding an efficient algorithm for any NP-complete problem implies that an efficient algorithm can be found for all NP problems, since a solution for any problem belonging to this class can be recast into a solution for any other member of the class. In 1971 American computer scientist Stephen Cook proved that the satisfiability problem (a problem of assigning values to variables in a formula in Boolean algebra such that the statement is true) is NP-complete, which was the first problem shown to be NP-complete and opened the way to showing other problems that are members of the class of NP-complete problems. A famous example of an NP-complete problem is the traveling salesman problem, which has wide applications in the optimization of transportation schedules. It is not known whether any polynomial time algorithms will ever be found for NP-complete problems, and determining whether these problems are tractable or intractable remains one of the most important questions in theoretical computer science. Such a discovery would prove that P = NP = NP-complete and revolutionize many fields in computer science and mathematics.
" height="20" alt="HEW Logo">
For example, modern cryptography relies on the assumption that factoring the product of two large prime numbers is not P. Note that verifying the product of two prime numbers is easy (polynomial time), but computing the two prime factors is hard. The discovery of an efficient algorithm for factoring large numbers would break most modern encryption schemes.
In 2000 American mathematician Stephen Smale devised an influential list of 18 important mathematical problems for solving in the 21st century. The third problem on his list was the P versus NP problem. Also in 2000 it was designated a Millennium Problem, one of seven mathematical problems selected by the Clay Mathematics Institute of Cambridge, Massachusetts, U.S., for a special award. The solution for each Millennium Problem is worth $1 million.