Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "P versus NP"

m (→‎Overview)
(clarified a number of points which were vague/incorrect)
Line 1: Line 1:
−
'''<math>P</math> versus <math>NP</math>''' is one of the greatest [[computability and complexity]] problems of modern mathematics, and one of the [[Millennium Problems]]. <math>P</math> stands for [[polynomial]], and it represents the category of problems for which there is an [[algorithm]] such that a computer could process it. <math>NP</math> stands for non-deterministic polynomial, and it represents problems such that a computer could not solve with a straightforward general algorithm.
+
'''<math>P</math> versus <math>NP</math>''' is one of the greatest [[computability and complexity]] problems of modern mathematics, and one of the [[Millennium Problems]]. <math>P</math> stands for [[polynomial]], and it represents the category of problems that can be solved by a deterministic algorithm in polynomial time. <math>NP</math> stands for non-deterministic polynomial, and it represents problems that can be solved by a non-deterministic algorithm in polynomial time.  Since all modern computers (with the exception of a few quantum computers) are deterministic, non-deterministic algorithms are not very useful, and many problems that would be solved in polynomial time on a non-deterministic machine end up taking exponential time.
  
 
==Overview==
 
==Overview==
Line 16: Line 16:
  
 
==Arguments==
 
==Arguments==
−
An important role in this discussion is played by the set of <math>NP</math>-complete problems (or <math>NPC</math>) which can be loosely described as the hardest problems in <math>NP</math> and therefore they are the least likely to be in P. More precisely, any problem in <math>NP</math>, through some efficient (takes at most a polynomial-bounded number of steps) transformation, can be expressed as a problem in <math>NP</math>-complete. Therefore if one finds an efficient (again, polynomial-bounded) solution to any <math>NP</math>-complete problem, then every problem in <math>NP</math> can be solved efficiently and therefore must be in <math>P</math>, hence proving <math>P = NP</math>. (See <math>NP</math>-complete for the exact definition.) Most theoretical computer scientists currently believe that the relationship among the classes <math>P</math>, <math>NP</math>, and <math>NPC</math> is as shown in the picture, with the P and NPC classes disjoint.
+
An important role in this discussion is played by the set of <math>NP</math>-complete problems (or <math>NPC</math>) which can be loosely described as the hardest problems in <math>NP</math>. More precisely, any problem in <math>NP</math>, through some efficient (takes at most a polynomial-bounded number of steps) transformation, can be expressed as a problem in <math>NP</math>-complete. Therefore if one finds an efficient (again, polynomial-bounded) solution to any <math>NP</math>-complete problem, then every problem in <math>NP</math> can be solved efficiently and therefore must be in <math>P</math>, hence proving <math>P = NP</math>. (See <math>NP</math>-complete for the exact definition.) Most theoretical computer scientists currently believe that the relationship among the classes <math>P</math>, <math>NP</math>, and <math>NPC</math> is as shown in the picture, with the P and NPC classes disjoint.
  
 
In essence, the <math>P = NP</math> question asks: if positive solutions to a <math>YES/NO</math> problem can be verified quickly, can the answers also be computed quickly? Here is an example to get a feeling for the question. Given a set of integers, does any subset of them sum to 0? For instance, does a subset of the set <math>\{-2, -3, 8, 15, -10\}</math> add up to <math>0</math>? The answer is <math>YES</math>, though it may take a little while to find a subset that does - and if the set was larger, it might take a very long time to find a subset that does. On the other hand, if someone claims that the answer is <math>YES</math>, because <math>\{-2, -3, -10, 15\}</math> add up to zero, then we can quickly check that with a few additions. Verifying that the subset adds up to zero is much faster than finding the subset in the first place. The information needed to verify a positive answer is also called a certificate. So we conclude that given the right certificates, positive answers to our problem can be verified quickly (i.e. in polynomial time) and that's why this problem is in <math>NP</math>.
 
In essence, the <math>P = NP</math> question asks: if positive solutions to a <math>YES/NO</math> problem can be verified quickly, can the answers also be computed quickly? Here is an example to get a feeling for the question. Given a set of integers, does any subset of them sum to 0? For instance, does a subset of the set <math>\{-2, -3, 8, 15, -10\}</math> add up to <math>0</math>? The answer is <math>YES</math>, though it may take a little while to find a subset that does - and if the set was larger, it might take a very long time to find a subset that does. On the other hand, if someone claims that the answer is <math>YES</math>, because <math>\{-2, -3, -10, 15\}</math> add up to zero, then we can quickly check that with a few additions. Verifying that the subset adds up to zero is much faster than finding the subset in the first place. The information needed to verify a positive answer is also called a certificate. So we conclude that given the right certificates, positive answers to our problem can be verified quickly (i.e. in polynomial time) and that's why this problem is in <math>NP</math>.
  
 
The restriction to <math>YES/NO</math> problems doesn't really make a difference; even if we allow more complicated answers, the resulting problem (whether <math>FP = FNP</math>) is equivalent.
 
The restriction to <math>YES/NO</math> problems doesn't really make a difference; even if we allow more complicated answers, the resulting problem (whether <math>FP = FNP</math>) is equivalent.

Revision as of 16:51, 17 June 2008

$P$ versus $NP$ is one of the greatest computability and complexity problems of modern mathematics, and one of the Millennium Problems. $P$ stands for polynomial, and it represents the category of problems that can be solved by a deterministic algorithm in polynomial time. $NP$ stands for non-deterministic polynomial, and it represents problems that can be solved by a non-deterministic algorithm in polynomial time. Since all modern computers (with the exception of a few quantum computers) are deterministic, non-deterministic algorithms are not very useful, and many problems that would be solved in polynomial time on a non-deterministic machine end up taking exponential time.

Overview

The relation between the complexity classes $P$ and $NP$ is one of the most important open problems in theoretical computer science and mathematics. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem). In such analysis, a model of the computer for which time must be analyzed is required. Typically, such models assume that the computer is deterministic - that, given the computer's present state and any inputs, there is only one possible action that the computer might take - and sequential - it performs actions one after the other. These assumptions reflect the behaviour of all practical computers yet devised, even including machines featuring parallel processing.

In this theory, the class $P$ consists of all those decision problems that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class $NP$ consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.

Importance

Arguably, the biggest open question in theoretical computer science concerns the relationship between those two classes: 

Is $P$ equal to $NP$?

In a 2002 poll of 100 researchers, 61 believed the answer is no, 9 believed the answer is yes, 22 were unsure, and 8 believed the question may be independent of the currently accepted axioms, and so impossible to prove or disprove.

The Clay Mathematics Institute has offered a USD <dollar/>1,000,000 prize for a correct solution, as it has listed it as one of its Millenium Problems.

Arguments

An important role in this discussion is played by the set of $NP$-complete problems (or $NPC$) which can be loosely described as the hardest problems in $NP$. More precisely, any problem in $NP$, through some efficient (takes at most a polynomial-bounded number of steps) transformation, can be expressed as a problem in $NP$-complete. Therefore if one finds an efficient (again, polynomial-bounded) solution to any $NP$-complete problem, then every problem in $NP$ can be solved efficiently and therefore must be in $P$, hence proving $P = NP$. (See $NP$-complete for the exact definition.) Most theoretical computer scientists currently believe that the relationship among the classes $P$, $NP$, and $NPC$ is as shown in the picture, with the P and NPC classes disjoint.

In essence, the $P = NP$ question asks: if positive solutions to a $YES/NO$ problem can be verified quickly, can the answers also be computed quickly? Here is an example to get a feeling for the question. Given a set of integers, does any subset of them sum to 0? For instance, does a subset of the set $\{-2, -3, 8, 15, -10\}$ add up to $0$? The answer is $YES$, though it may take a little while to find a subset that does - and if the set was larger, it might take a very long time to find a subset that does. On the other hand, if someone claims that the answer is $YES$, because $\{-2, -3, -10, 15\}$ add up to zero, then we can quickly check that with a few additions. Verifying that the subset adds up to zero is much faster than finding the subset in the first place. The information needed to verify a positive answer is also called a certificate. So we conclude that given the right certificates, positive answers to our problem can be verified quickly (i.e. in polynomial time) and that's why this problem is in $NP$.

The restriction to $YES/NO$ problems doesn't really make a difference; even if we allow more complicated answers, the resulting problem (whether $FP = FNP$) is equivalent.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=P_versus_NP&oldid=26634"