Encyclopedia > NP-easy

  Article Content

NP-easy

In complexity theory, NP-easy is a set of problems similar to NP, except that NP-easy problems do not have to be decision problems.

A problem X is in NP-easy if and only if there exists some problem Y in NP such that X is Turing reducible[?] to Y. This means that given a black box that solves instances of Y in unit time, there exists an algorithm that solves X in polynomial time by repeatedly using that black box.

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 used 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. NP-hard also uses a Turing reduction, for the same reason.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Christiania

... of Christiania - a partially self-governing neighborhood in the city of Copenhagen. This is a disambiguation page; that is, one that just points to other pages that ...

 
 
 
This page was created in 36.7 ms