|
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.〔, p. 117, 120.〕 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== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「NP-easy」の詳細全文を読む スポンサード リンク
|