P versus NP

$P$ versus $NP$ is one of the greatest computability and complexity problems of modern mathematics, and one of the Millennium Problems. $P$ the class of decision problems (those whose answer is either "yes" or "no," as opposed to other classes such as counting problems) that can be solved by a deterministic algorithm in polynomial time. $NP$ is the class of decision problems that can be solved by a non-deterministic algorithm in polynomial time. The $P$ versus $NP$ question asks whether these two classes are the same, or whether there are problems in $NP$ that are not in $P$ .

Since all modern computers (with the exception of a few quantum computers) are deterministic, non-deterministic algorithms are of theoretical, rather than practical, interest. However, the class $NP$ can also be defined without reference to nondeterminism: This article is a stub. Help us out by expanding it.

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 $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$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)YES/NO $problems doesn't really make a difference; even if we allow more complicated answers, the resulting problem (whether$ FP = FNP$) is equivalent.

Page

Toolbox

Search

P versus NP

Overview

Importance