# 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

**if there exists a Turing machine program**

*P**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

**then there is no algorithm that recognizes it and is guaranteed to be always “fast”.**

*P***P is the class of languages that are recognizable in polynomial time on a nondeterministic Turing machine.**

*N*Clearly

**⊆**

*P***P**

*N*but the question of whether or not

**=**

*P***P**

*N*has not been solved despite a great amount of research.

Contained in

**P is a set**

*N**NPC*of languages that are called

*NP-complete*. A language

*L*

_{1}is in

*NPC*if every language

*L*

_{2}in

**P can be polynomially reduced to**

*N**L*

_{1}, i.e. there is some function

*f*such that

(a)

*x*∈

*L*

_{1}iff

*f*(

*x*) ∈

*L*

_{2}

(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

**then**

*P***=**

*P***P.**

*N*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***P.**

*N*A language is said to be

*NP-hard*if any language in

**P can be polynomially reduced to it, even if the language itself is not in**

*N***P.**

*N*#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**P=NP question**