NP-easy

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

  1. Garey & Johnson (1979), p. 117, 120.
gollark: IoT is great because it makes efficient use of computing resources - previously, a toaster could just sit there unhelpfully. *Now* it DDOSes people and mines bitcoins.
gollark: Of course not. They'll do 6GHz but slower due to security issue mitigations!
gollark: Quantum stuff doesn't matter. It's the fact that everything is horrendously insecure anyway.
gollark: I'm sure there are loads, but nobody uses them.
gollark: ```Python 3.7.0 (default, Jul 15 2018, 10:44:58) [GCC 8.1.1 20180531] on linuxType "help", "copyright", "credits" or "license" for more information.>>> [a^a for a in range(10)][0, 0, 0, 0, 0, 0, 0, 0, 0, 0]>>> [a**a for a in range(10)][1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489]>>> ```

References

  • Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.