Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/NP-easy> ?p ?o }
Showing triples 1 to 36 of
36
with 100 triples per page.
- NP-easy abstract "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 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.".
- NP-easy wikiPageID "54688".
- NP-easy wikiPageLength "1748".
- NP-easy wikiPageOutDegree "17".
- NP-easy wikiPageRevisionID "541369786".
- NP-easy wikiPageWikiLink Category:Complexity_classes.
- NP-easy wikiPageWikiLink Complexity_class.
- NP-easy wikiPageWikiLink Computational_complexity_theory.
- NP-easy wikiPageWikiLink Decision_problem.
- NP-easy wikiPageWikiLink Function_problem.
- NP-easy wikiPageWikiLink If_and_only_if.
- NP-easy wikiPageWikiLink Many-one_reduction.
- NP-easy wikiPageWikiLink NP-equivalent.
- NP-easy wikiPageWikiLink NP_(complexity).
- NP-easy wikiPageWikiLink Oracle_machine.
- NP-easy wikiPageWikiLink Polynomial-time_reduction.
- NP-easy wikiPageWikiLink Polynomial_hierarchy.
- NP-easy wikiPageWikiLink Quicksort.
- NP-easy wikiPageWikiLink Time_complexity.
- NP-easy wikiPageWikiLink Turing_machine.
- NP-easy wikiPageWikiLinkText "NP-easy".
- NP-easy wikiPageUsesTemplate Template:Garey-Johnson.
- NP-easy wikiPageUsesTemplate Template:Reflist.
- NP-easy subject Category:Complexity_classes.
- NP-easy hypernym Set.
- NP-easy type Class.
- NP-easy comment "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.".
- NP-easy label "NP-easy".
- NP-easy sameAs Q505373.
- NP-easy sameAs NP-leicht.
- NP-easy sameAs NP-fácil.
- NP-easy sameAs m.0f88v.
- NP-easy sameAs Q505373.
- NP-easy sameAs NP-易.
- NP-easy wasDerivedFrom NP-easy?oldid=541369786.
- NP-easy isPrimaryTopicOf NP-easy.