P=NP question

P=NP question 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 T_M(n) ← p(n)

for all nonnegative integers n, where T_M 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 P ⊆ NP

but the question of whether or not P = NP

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 L₁ is in NPC if every language L₂ in NP can be polynomially reduced to L₁, i.e. there is some function f such that

(a) x ∈ L₁ iff f(x) ∈ L₂

(b) f(x) is computable by a Turing machine in time bounded by a polynomial in the length of x.

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.