Encyclopedia > NP

  Article Content


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
List of battles 1801-1900

... Battle of Adowa Mar. 1 Abessinia (Ethiopia) defeats Italy 1898 Battle of Manila Bay May 1 Dewey says "You may fire when you are ready Gridley" 1898 Battle of L ...