Lesson plan

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. 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 FP NP (see the function problem article) or for FΔ 2 P (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.

Back to article

Article summary

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. 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 FP NP (see the function problem article) or for FΔ 2 P (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.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.