## Quick Reference

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”.

*T*_{M}(*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 *L*_{1} is in **NPC** if every language *L*_{2} in NP can be polynomially reduced to *L*_{1}, i.e. there is some function *f* such that*x* ∈ *L*_{1} iff *f*(*x*) ∈ *L*_{2}*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*.

*x* ∈ *L*_{1} iff *f*(*x*) ∈ *L*_{2}

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

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

**From:**
P=NP question
in
A Dictionary of Computing »

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.