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 TM(n) ≤ p(n) 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”.
TM(n) ≤ p(n)
NP is the class of languages that are recognizable in polynomial time on a nondeterministic Turing machine.
Clearly P ⊆ NP but the question of whether or not P = NP has not been solved despite a great amount of research.
P ⊆ NP
P = NP
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
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.