NP-easy

related topics
{math, number, function}

In complexity theory, the complexity class NP-easy is the set of function problems 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.[1] 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.

Notes

References

Full article ▸

related documents
Monoid ring
Continuity property
HTML scripting
EXPSPACE
Almost everywhere
Wikipedia:Searching bug reports
Laurent polynomial
Catalan's constant
Krull dimension
Gauss–Legendre algorithm
Self-similarity
Weak entity
Integer sequence
Probability axioms
Two-out-of-five code
Timeline of programming languages
Pole (complex analysis)
Linear congruence theorem
Senary
Permutation group
Partition of unity
Composite number
Almost all
Leaf node
Group homomorphism
Power associativity
Prime ideal
Multiple inheritance
Co-NP-complete
Mary (programming language)