Overview

P=NP question


Show Summary Details

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 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 PNP but the question of whether or not P = NP has not been solved despite a great amount of research.

PNP

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)xL1 iff f(x) ∈ L2(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)xL1 iff f(x) ∈ L2

(b)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 PNP.

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.

Subjects: Computing.


Reference entries

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