# Difference between revisions of "P versus NP"

(wikify) |
m (→Overview) |
||

Line 2: | Line 2: | ||

==Overview== | ==Overview== | ||

− | The relation between the complexity classes <math>P</math> and <math>NP</math> 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 | + | The relation between the complexity classes <math>P</math> and <math>NP</math> 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 <math>P</math> 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 <math>NP</math> 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]]. | In this theory, the class <math>P</math> 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 <math>NP</math> 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]]. |

## Revision as of 13:40, 28 October 2007

** versus ** is one of the greatest computability and complexity problems of modern mathematics, and one of the Millennium Problems. stands for polynomial, and it represents the category of problems for which there is an algorithm such that a computer could process it. stands for non-deterministic polynomial, and it represents problems such that a computer could not solve with a straightforward general algorithm.

## Overview

The relation between the complexity classes and 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 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 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 equal to ?

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 -complete problems (or ) which can be loosely described as the hardest problems in and therefore they are the least likely to be in P. More precisely, any problem in , through some efficient (takes at most a polynomial-bounded number of steps) transformation, can be expressed as a problem in -complete. Therefore if one finds an efficient (again, polynomial-bounded) solution to any -complete problem, then every problem in can be solved efficiently and therefore must be in , hence proving . (See -complete for the exact definition.) Most theoretical computer scientists currently believe that the relationship among the classes , , and is as shown in the picture, with the P and NPC classes disjoint.

In essence, the question asks: if positive solutions to a 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 add up to ? The answer is , 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 , because 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 .

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