
related topics 
{math, number, function} 
{law, state, case} 
{line, north, south} 
{city, population, household} 

In computational complexity theory, NP is one of the most fundamental complexity classes. The abbreviation NP refers to "nondeterministic polynomial time".
Intuitively, NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes". More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine. In an equivalent formal definition, NP is the set of decision problems where the "yes"instances can be recognized in polynomial time by a nondeterministic Turing machine. The equivalence of the two definitions follows from the fact that an algorithm on such a nondeterministic machine consists of two phases, the first of which consists of a guess about the solution which is generated in a nondeterministic way, while the second consists of a deterministic algorithm which verifies or rejects the guess as a valid solution to the problem.^{[2]}
The complexity class P is contained in NP, but NP contains many important problems, the hardest of which are called NPcomplete problems, for which no polynomialtime algorithms are known. The most important open question in complexity theory, the P = NP problem, asks whether such algorithms actually exist for NPcomplete, and by corollary, all NP problems. It is widely believed that this is not the case.^{[3]}
Contents
Formal definition
The complexity class NP can be defined in terms of NTIME as follows:
Alternatively, NP can be defined using deterministic Turing machines as verifiers. A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that
Full article ▸


related documents 
Direct product 
Greatest common divisor 
Polish notation 
Empty set 
Binomial theorem 
Net (mathematics) 
Ordered pair 
Partially ordered set 
Affine transformation 
Tensor 
Graph theory 
Normal space 
Grover's algorithm 
Knapsack problem 
Topological vector space 
Bspline 
Cyclic group 
A* search algorithm 
Fundamental theorem of arithmetic 
Banach space 
Selection sort 
Sheffer stroke 
Universal quantification 
Free group 
Delaunay triangulation 
Pell's equation 
Optimization (mathematics) 
Befunge 
Document Type Definition 
Brute force attack 
