Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP-complete in this case was established by Ladner. ^[1]

In computational complexity theory, NP is one of the most fundamental complexity classes. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources In Computational complexity theory, a complexity class is a set of problems of related complexity The abbreviation NP refers to "Non-deterministic Polynomial time".

Intuitively, NP contains all decision problems for which the 'yes'-answers have simple proofs of the fact that the answer is indeed 'yes'. In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine. Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm In an equivalent formal definition, NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine. In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on In Theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers

The complexity class P is contained in NP, but NP contains many important problems, called NP-complete problems, for which no polynomial-time algorithms are known. In Computational complexity theory, P, also known as PTIME or DTIME ( n O(1 is one of the most fundamental Complexity In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation The most important open question in complexity theory, the P = NP problem, asks whether such algorithms actually exist for NP-complete problems. The relationship between the Complexity classes P and NP is an unsolved question in Theoretical computer science. It is widely believed that this is not the case.

Formal definition

The complexity class NP can be defined in terms of NTIME as follows:

Introduction

Many natural computer science problems are covered by the class NP. In Computational complexity theory, the Complexity class NTIME(f(n is the set of Decision problems that can be solved by a Non-deterministic Turing Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their In particular, the decision versions of many interesting search problems and optimization problems are contained in NP.

Verifier-based definition

In order to explain the verifier-based definition of NP, let us consider the subset sum problem: Assume that we are given some integers, such as {−7, −3, −2, 5, 8}, and we wish to know whether some of these integers sum up to zero. In Computer science, the subset sum problem is an important problem in complexity theory and Cryptography. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In this example, the answer is 'yes', since the subset of integers {-3, -2, 5} corresponds to the sum (-3) + (-2) + 5 = 0. The task of deciding whether such a subset with sum zero exists is called the subset sum problem.

As the number of integers that we feed into the algorithm becomes larger, the time needed to compute the answer to the subset sum problem grows exponentially, and in fact the subset sum problem is NP-complete. However, notice that, if we are given a particular subset (often called a certificate,) we can easily check or verify whether the subset sum is zero, by just summing up the integers of the subset. So if the sum is indeed zero, that particular subset is the proof or witness for the fact that the answer is 'yes'. An algorithm that verifies whether a given subset has sum zero is called verifier. A problem is said to be in NP iff there exists a verifier for the problem that executes in polynomial time. ↔ In case of the subset sum problem, the verifier needs only polynomial time, for which reason the subset sum problem is in NP.

Note that the verifier-based definition of NP does not require an easy-to-verify certificate for the 'no'-answers. The class of problems with such certificates for the 'no'-answers is called co-NP. In Computational complexity theory, co-NP is a Complexity class. In fact, it is an open question whether all problems in NP also have certificates for the 'no'-answers and thus are in co-NP.

Machine-definition

Equivalent to the verifier-based definition is the following characterization: NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine. In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on In Theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers

Examples

This is an incomplete list of further problems that are in NP.

• All problems in P
• The integer factorization problem of finding a number which (nontrivially) divides a given number, as in 6 = 2 × 3
• 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 can be true for some value of the variables or not

See NP-complete for a list of additional important problems in NP. In Computational complexity theory, P, also known as PTIME or DTIME ( n O(1 is one of the most fundamental Complexity In Graph theory, an isomorphism of graphs G and H is a Bijection between the vertex sets of G and H The Travelling salesman problem ( TSP) in Operations research is a problem in discrete or Combinatorial optimization. This is a technical mathematical article about the area of mathematical logic variously known as "propositional calculus" or "propositional logic" In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties

Why some NP problems are hard to solve

Because of the many important problems in this class, there have been extensive efforts to find polynomial-time algorithms for problems in NP. However, there remain a large number of problems in NP that defy such attempts, seeming to require superpolynomial time. Whether these problems really aren't decidable in polynomial time is one of the greatest open questions in computer science (see P=NP problem for an in-depth discussion). Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their The relationship between the Complexity classes P and NP is an unsolved question in Theoretical computer science.

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. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties 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.

Equivalency of definitions

The two definitions of NP as the class of problems solvable by a nondeterministic Turing machine (TM) in polynomial time and the class of problems verifiable by a deterministic Turing machine in polynomial time are equivalent. Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm The proof is described by many textbooks, for example Sipser's Introduction to the Theory of Computation, section 7. 3.

To show this, first suppose we have a deterministic verifier. A nondeterministic machine can simply nondeterministically run the verifier on all possible proof strings (this requires only polynomially-many steps because it can nondeterministically choose the next character in the proof string in each step, and the length of the proof string must be polynomially bounded). If any proof is valid, some path will accept; if no proof is valid, the string is not in the language and it will reject.

Conversely, suppose we have a nondeterministic TM called A accepting a given language L. At each of its polynomially-many steps, the machine's computation tree branches in at most a constant number of directions. A computation tree is a representation for the computation steps of a Non-deterministic Turing machine on a specified input There must be at least one accepting path, and the string describing this path is the proof supplied to the verifier. The verifier can then deterministically simulate A, following only the accepting path, and verifying that its accepts at the end. If A rejects the input, there is no accepting path, and the verifier will never accept.

Relationship to other classes

NP contains all problems in P, since one can verify any instance of the problem by simply ignoring the proof and solving it. In Computational complexity theory, P, also known as PTIME or DTIME ( n O(1 is one of the most fundamental Complexity NP is contained in PSPACE - to show this, it suffices to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial-time verifier. Mathematicians and computer scientists try to carefully define different types of complexity, and PSPACE is one of these types Since a polynomial-time machine can only read polynomially-many bits, it cannot use more than polynomial space, nor can it read a proof string occupying more than polynomial space (so we don't have to consider proofs longer than this). NP is also contained in EXPTIME, since the same algorithm operates in exponential time. "EXP" redirects here for other uses see Exp. In Computational complexity theory, the Complexity class EXPTIME

The complement of NP, co-NP, contains those problems which have a simple proof for no instances, sometimes called counterexamples. In Computational complexity theory, the complement of a Decision problem is the decision problem resulting from reversing the yes and no answers In Computational complexity theory, co-NP is a Complexity class. For example, primality testing trivially lies in co-NP, since one can refute the primality of an integer by merely supplying a nontrivial factor. A primality test is an Algorithm for determining whether an input number is prime. NP and co-NP together form the first level in the polynomial hierarchy, higher only than P. In Computational complexity theory, the polynomial hierarchy is a hierarchy of Complexity classes that generalize the classes P, NP

NP is defined using only deterministic machines. If we permit the verifier to be probabilistic (specifically, a BPP machine), we get the class MA solvable using a Arthur-Merlin protocol with no communication from Merlin to Arthur. In complexity theory, BPP is the class of Decision problems solvable by a Probabilistic Turing machine in Polynomial time, with an error In Computational complexity theory, an Arthur-Merlin protocol is an Interactive proof system in which the verifier's coin tosses are constrained to be public (i

NP is a class of decision problems; the analogous class of function problems is FNP. In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on In Computational complexity theory, the Complexity class FNP is the Function problem extension of the Decision problem class NP.

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. Fagin's theorem is a result in descriptive complexity theory which states that the set of all properties expressible in existential Second-order logic is precisely In Logic and Mathematics second-order logic is an extension of First-order logic, which itself is an extension of Propositional logic. In Predicate logic, universal quantification is an attempt to formalize the notion that something (a Logical predicate) is true for everything, or every

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. In Computational complexity theory, an interactive proof system is an Abstract machine that models Computation as the exchange of messages between two parties 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.

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)). In Computational complexity theory, PCP is the class of Decision problems having probabilistically checkable proof systems 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 Computer science and Operations research, approximation algorithms are Algorithms used to find approximate solutions to Optimization problems

Example

The decision version of the traveling salesman problem is in NP. The Travelling salesman problem ( TSP) in Operations research is a problem in discrete or Combinatorial optimization. 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:

• 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. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments

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. (Equivalently, this can be thought of as a single Turing machine that always guesses correctly)

Binary search on the range of possible distances can convert the decision version of Traveling Salesman to the optimization version, by calling the decision version repeatedly (a polynomial number of times). A binary search algorithm (or binary chop) is a technique for locating a particular value in a sorted list of values

References

1. ^ R. E. Ladner "On the structure of polynomial time reducibility," J. ACM, 22, pp. 151–171, 1975. Corollary 1. 1. ACM site.

• Complexity Zoo: NP
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Thomas H Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. Charles Eric Leiserson is a Computer scientist, specializing in the theory of Parallel computing and Distributed computing, and particularly practical Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer. Clifford Stein, a Computer scientist, is currently a professor of Industrial engineering and Operations research at Columbia University Introduction to Algorithms, Second Edition. Introduction to Algorithms is a book by Thomas H Cormen, Charles E MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34. 2: Polynomial-time verification, pp. 979–983.
• Michael Sipser (1997). Michael Fredric Sipser is a Professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. 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.
• David Harel, Yishai Feldman. David Harel (דוד הראל born 1950 is a Professor of Computer science at the Weizmann Institute of Science in Israel. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.