In computational complexity theory, NP ("Non-deterministic Polynomial time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. Equivalently, it is the set of problems that can be "verified" by a deterministic Turing machine in polynomial time; more detail below. In computer science, computational complexity theory is the branch of the theory of computation that studies the resources required during computation to solve a given problem. ... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ... In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... In theoretical computer science, an ordinary (deterministic) Turing machine (DTM) has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...

Introduction and applications

The importance of this class of decision problems is that it contains many interesting searching and optimization problems where we want to know if there exists a certain solution for a certain problem.

As a simple example, consider the problem of determining whether a number n is a composite number. For large numbers, this seems like a very difficult problem to solve efficiently; the simplest approaches require time which is exponential in log n, the number of input bits. On the other hand, once we've found a candidate factor of n, the following function can quickly tell us whether it really is a factor: A composite number is a positive integer which has a positive divisor other than one or itself. ...

 boolean isNontrivialFactor(n, d) if n is divisible by d and d ≠ 1 and d ≠ n return true else return false 

If n is composite, then this function will return true for some input d. If n is prime, however, this function will always return false, regardless of d. All problems in NP have a deterministic function just like this, which accepts only when given both an input and proof that the input is in the language. We must be able to check if the proof is correct in polynomial time. We call such a machine a verifier for the problem.

If we have a nondeterministic machine, testing a number for compositeness is easy. It can branch into n different paths in just O(log n) steps (see Big O notation); then, each of these can call isNontrivialFactor(n, d) for one d. If any succeed, the number is composite; otherwise, it is prime. Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

Thus, the challenge of NP problems is to efficiently find the answer, given an efficient (polynomial-time) way of verifying it once it is found. This challenge was solved (see AKS Primality Test) for compositeness testing only in 2002; there is still no known polynomial-time way to solve the more general factoring problem of determining whether a number between 1 and m divides n. The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by three Indian scientists named Manindra Agrawal, Neeraj Kayal and Nitin Saxena on August 6, 2002 in a scientific paper titled PRIMES is in P... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ...

But these are only some of the easiest problems in NP. Additional examples include:

• The graph isomorphism problem of determining whether two graphs can be drawn identically
• The traveling salesman problem, where we want to know if there is a route of some length that goes through all the nodes in a certain network
• The boolean satisfiability problem, where we want to know if a certain formula in propositional logic with boolean variables is satisfiable or not

See NP-complete for a list of additional important problems in NP. In computational complexity theory, the graph isomorphism problem or GI problem is the graph theory problem of determining whether, given two graphs G1 and G2, it is possible to permute (or relabel) the vertices of one graph so that it is equal to the other. ... The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ... The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. ... A propositional calculus is a formal, deduction system, or proof theory for reasoning with propositional formulas as symbolic logic. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

Why some NP problems are hard to solve

Because of the many important problems in this class, there have been extensive efforts to find algorithms that decide the problems in NP in time which is polynomial in the input size, which is generally considered efficient. However, there are a large number of problems in NP that defy such attempts, seeming to require superpolynomial time. Whether these problems really aren't solvable in polynomial time is one of the greatest open questions in computer science (see Complexity classes P and NP for an in-depth discussion). Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Diagram of complexity classes provided that P ≠ NP. If P = NP, then all three classes are equal. ...

An important notion in this context is the set of NP-Complete decision problems, which is a subset of NP and might be informally described as the "hardest" problems in NP. If there is a polynomial-time algorithm for even one of them, then there is a polynomial-time algorithm for all the problems in NP. Because of this, and because dedicated research has failed to find a polynomial algorithm for any NP-complete problem, once a problem has been proven to be NP-complete this is widely regarded as a sign that a polynomial algorithm for this problem is unlikely to exist. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

Other characterizations

There is also a simple logical characterization of NP: it contains precisely those languages expressible in second order logic restricted to exclude universal quantification over relations, functions, and subsets. In mathematical logic, second-order logic is an extension of either propositional logic or first-order logic which contains variables in predicate positions (rather than only in term positions, as in first-order logic), and quantifiers binding them. ... In predicate logic, universal quantification is an attempt to formalise the notion that something (a logical predicate) is true for everything, or every relevant thing. ...

NP can be seen as a very simple type of interactive proof system, where the prover comes up with the proof certificate and the verifier is a deterministic polynomial-time machine that checks it. It is complete because the right proof string will make it accept if there is one, and it is sound because the verifier cannot accept if there is no acceptable proof string. In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. ...

A major result of complexity theory is that NP can be characterized as the problems solvable by probabilistically checkable proofs where the verifier uses O(log n) random bits and examines only a constant number of bits of the proof string (the class PCP(log n, 1)). More informally, this means that the NP verifier described above can be replaced with one that just "spot-checks" a few places in the proof string, and using a limited number of coin flips can determine the correct answer with high probability. This allows several results about the hardness of approximation algorithms to be proven. In computational complexity theory, PCP is the class of decision problems having probabilistically checkable proof systems. ... In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ...

Example

The decision version of the traveling salesperson problem is in NP. Given an input matrix of distances between N cities, the problem is to determine if there is a route visiting all cities with total distance less than k. A nondeterministic Turing machine can find such a route as follows: The traveling salesman problem (TSP), also known as the traveling salesperson problem, is a problem in discrete or combinatorial optimization. ...

• At each city it visits it "guesses" the next city to visit, until it has visited every vertex. If it gets stuck, it stops immediately.
• At the end it verifies that the route it has taken has cost less than k in O(n) time.

One can think of each guess as "forking" a new copy of the Turing machine to follow each of the possible paths forward, and if at least one machine finds a route of distance less than k, that machine accepts the input. The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

What makes this a natural decision version of the problem is that, if we could solve this problem quickly, we could use binary search to solve the original computation problem (finding the route and its exact length) quickly as well. In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ...

References

• Complexity Zoo: NP
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 34.2: Polynomial-time verification, pp.979–983.
• Michael Sipser (1997). Introduction to the Theory of Computation, PWS Publishing. ISBN 0-534-94728-X. Sections 7.3–7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp.241–271.

Famous coauthor of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ... Michael Sipser is a Professor of Applied Mathematics in the Theory of Computation Group at MIT. His research area is complexity theory. ...