P Problem

Informally the class P is the class of decision problems solvable by some algorithms within a number of steps bounded by some fixed polynomial in the length of the input.

To define the problem precisely it is necessary to give a formal model of a computer. The standard computer model in computability theory is the Turing machine, introduced by Alan Turing in 1936 [Turing 36]. Although the model was introduced before physical computers were built, it nevertheless continues to be accepted as the proper computer model for the purpose of defining the notion of computable function.

Formally the elements of the class P are languages. We define the class P of languages as:

for some Turing machine in polynomial time

Where

• L is a subset of , being the set of finite strings over , a finite alphabet with at least two elements.
• M is a Turing machine with an associated input alphabet .
• L(M) is the language accepted by M. It has an associated alphabet and is defined by ; M accepts w (a string in ) if its computation terminates in the accepting state.

NP Problem

NP is not the same as non-P. The notation NP stands for “nondeterministic polynomial time”, since originally NP was defined in terms of nondeterministic machines (that is, machines that have more than one possible move from a given configuration).

A problem is assigned to the NP class if it is solvable in polynomial time by a nondeterministic Turing machine (a nondeterministic Turing machine is a "parallel" Turing machine which can take many computational paths simultaneously, with the restriction that the parallel Turing machines cannot communicate).

A P problem (whose solution time is bounded by a polynomial) is always also NP. If a problem is known to be NP, and a solution to the problem is somehow known, then demonstrating the correctness of the solution can always be reduced to a single P (polynomial time) verification. If P and NP are not equivalent, then the solution of NP-problems requires (in the worst case) an exhaustive search.

NP-Hard Problem

A problem is NP-hard (Non-deterministic Polynomial-time Hard) if solving it in polynomial time would make it possible to solve all problems in class NP in polynomial time . That is, a problem is NP-hard if an algorithm for solving it can be translated into one for solving any other NP problem (nondeterministic polynomial time) problem. NP-hard therefore means "at least as hard as any NP problem".

NP-Complete Problem

A decision problem C is NP-complete if it is in NP and if every other problem in NP is reducible to it [Cook 1971]. "Reducible" here means that for every NP problem L, there is a polynomial time algorithm which transforms instances of L into instances of C, such that the two instances have the same truth values. As a consequence, if we had a polynomial time algorithm for C, we could solve all NP problems in polynomial time.