Encyclopedia: NPE...

Encyclopedia : N : NP : NPE (3 articles)

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 tha..

NP-equivalent
In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems. For example, the problem FIND-SUBSET-SUM is in NP-equivalent. Given a set of integers, FIND..

From Wikipedia, the Free Encyclopedia. Article contents subject to the GNU Free Documentation License.