NP-easy
Encyclopedia
In complexity theory
, the complexity class
NP-easy is the set of function problem
s that are solvable in polynomial time by a deterministic Turing machine with an oracle
for some decision problem
in NP
.
In other words, a problem X is NP-easy if and only if
there exists some problem Y in NP such that X is polynomial-time Turing reducible to Y. This means that given an oracle
for Y, there exists an algorithm that solves X in polynomial time (possibly by repeatedly using that oracle).
NP-easy is another name for FPNP (see the function problem
article) or for FΔ2P (see the polynomial hierarchy
article).
An example of an NP-easy problem is the problem of sorting a list of strings. The decision problem "is string A greater than string B" is in NP. There are algorithms such as Quicksort that can sort the list using only a polynomial number of calls to the comparison routine, plus a polynomial amount of additional work. Therefore, sorting is NP-easy.
There are also more difficult problems that are NP-easy. See NP-equivalent
for an example.
The definition of NP-easy uses a Turing reduction rather than a many-one reduction
because the answers to problem Y are only TRUE or FALSE, but the answers to problem X can be more general. Therefore, there is no general way to translate an instance of X to an instance of Y with the same answer.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
NP-easy is the set of function problem
Function problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
s that are solvable in polynomial time by a deterministic Turing machine with an oracle
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
for some decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
in NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
.
In other words, a problem X is NP-easy if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
there exists some problem Y in NP such that X is polynomial-time Turing reducible to Y. This means that given an oracle
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
for Y, there exists an algorithm that solves X in polynomial time (possibly by repeatedly using that oracle).
NP-easy is another name for FPNP (see the function problem
Function problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
article) or for FΔ2P (see the polynomial hierarchy
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
article).
An example of an NP-easy problem is the problem of sorting a list of strings. The decision problem "is string A greater than string B" is in NP. There are algorithms such as Quicksort that can sort the list using only a polynomial number of calls to the comparison routine, plus a polynomial amount of additional work. Therefore, sorting is NP-easy.
There are also more difficult problems that are NP-easy. See NP-equivalent
NP-equivalent
In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems....
for an example.
The definition of NP-easy uses a Turing reduction rather than a many-one reduction
Many-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
because the answers to problem Y are only TRUE or FALSE, but the answers to problem X can be more general. Therefore, there is no general way to translate an instance of X to an instance of Y with the same answer.