Nondeterministic Polynomial Time

What is Non-deterministic Polynomial Time?

NP, for non-deterministic polynomial time, is one of the best-known complexity classes in theoretical computer science. A decision problem (a problem that has a yes/no answer) is said to be in NP if it is solvable in polynomial time by a non-deterministicTuring machine. Equivalently, and more intuitively, a decision problem is in NP if, if the answer is yes, a proof can be verified by a Turing machine in polynomial time.

A Practical Example

An easy example of this is Sudoku. To phrase it as a decision problem, you would say something like, "Given a sudoku puzzle, does it have a solution?" It may take a long time to answer that question (because you have to solve the puzzle), but if someone gives you a solution you can very quickly verify that the solution is correct. That's what NP is -- the set of all decision problems where you can efficiently verify the answer.

In contrast, P (polynomial time) is the set of all decision problems which can be solved in polynomial time by a Turing machine. Roughly speaking, if a problem is in P, then it's considered tractable, i.e. there exists an algorithm that can solve it in a reasonable amount of time on a computer. If a problem is not in P, then it's said to be intractable, meaning that for large values it would take far too long for even the best supercomputer to solve it - in some cases, this means millions or even billions of years.

In Computer Science and Machine Learning

An open question in theoretical computer science is whether P = NP. If P and NP were shown to be identical, then that would mean that all of the problems in NP are also in P -- i.e. that some algorithm exists to solve any given problem in NP quickly. This would be earth shattering because there are a lot of problems in NP that it would be convenient to be able to solve quickly, and also because all of cryptography is based on the assumption that certain problems in NP are too difficult for anyone to solve in a reasonable amount of time. Conversely, if we had a proof that P ≠ NP, then we would know for certain that there are certain problems (the NP-complete problems) which have no quick solutions.

Examples of NP problems include:

  • Calculating the greatest common divisor of a number (this is in P)
  • Linear programming (this is in P)
  • The subgraph isomorphism problem: given a graph G and a graph H, does G contain a subgraph that's isomorphic to H? (this is in NP)
  • Given a set of points, does there exist some route that goes through each point of a length less than k? (Travelling Salesman Problem; this is in NP-complete)

We care about this in AI because there are quite a few problems that crop up in AI that are in NP.