One of the major open questions in theoretical computer science at present.
P is the class of formal languages that are recognizable in polynomial time. More precisely a language L is in P if there exists a Turing machine program M and a polynomial p(n) such that M recognizes L and
for all nonnegative integers
n, where
TM is the time complexity of
M (
see complexity measure). It is generally accepted that if a language is not in
P then there is no algorithm that recognizes it and is guaranteed to be always ‘fast’.
NP is the class of languages that are recognizable in polynomial time on a nondeterministic Turing machine.
Clearly
but the question of whether or not
has not been solved despite a great amount of research.
Contained in NP is a set NPC of languages that are called NP-complete. A language L1 is in NPC if every language L2 in NP can be polynomially reduced to L1, i.e. there is some function f such that
It can be shown that if any NP-complete language is also in
P then
P=
NP.
A wide variety of problems occurring in computer science, mathematics, and operations research are now known to be NP-complete. As an example the problem of determining whether a Boolean expression in conjunctive normal form (see conjunction) can be satisfied by a truth assignment was the first problem found to be NP-complete; this is generally referred to as the satisfiability (or CNF satisfiability) problem. Despite considerable effort none of these NP-complete problems have been shown to be polynomially solvable. Thus it is widely conjectured that no NP-complete problem is polynomially solvable and P ≠ NP.
A language is said to be NP-hard if any language in NP can be polynomially reduced to it, even if the language itself is not in NP.