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 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”.
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 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) x ∈ L1 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 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.
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”.
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 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) x ∈ L1 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 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.
More From encyclopedia.com
Formal Language , formal language
1. A language with explicit and precise rules for its syntax and semantics. Examples include programming languages and also logics su… Programming Language , In order for computers to accept commands from humans and perform tasks vital to productivity and e-commerce, a means of communication must exist. Pr… Pashto , Pashto (Pushto) One of the two major languages of Afghanistan, the other being Persian. Pashto is spoken by about 12 million people in e Afghanistan… International Language , international language, sometimes called universal language, a language intended to be used by people of different linguistic backgrounds to facilita… Cobol , Cobol
COBOL (COmputer Business Oriented Language), is a programming language used in many different business applications, both on mainframe computer… Computer Language , computer language System of words and rules used to program a computer. Most computers work using a binary-coded language (using 1s and 0s) called ma…
You Might Also Like
NEARBY TERMS
P=NP question