Encyclopedia > NP

  Article Content

NP

In complexity theory, NP ("Non-deterministic Polynomial-time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. Or, equivalently, YES answers are checkable in polynomial time on a deterministic Turing machine given the right information.

A language L belongs to NP if there exists a two input polynomial time algorithm A and a constant c such that

L = {x in {0,1} | ∃ certificate, y with |y| = O(xc) such that A(x,y) = 1}
Algorithm A verifies L in polynomial time.


See Complexity classes P and NP and NP-Complete.

Alternate use: NP is also the ISO country code for Nepal.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Lake Ronkonkoma, New York

... There are 6,949 housing units at an average density of 546.4/km² (1,414.4/mi²). The racial makeup of the town is 93.53% White, 1.36% African ...

 
 
 
This page was created in 32.8 ms