Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Turing_reduction> ?p ?o }
Showing triples 1 to 88 of
88
with 100 triples per page.
- Turing_reduction abstract "In computability theory, a Turing reduction from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for B. Turing reductions can be applied to both decision problems and function problems. If a Turing reduction of A to B exists then every algorithm for B can be used to produce an algorithm for A, by inserting the algorithm for B at each place where the oracle machine computing A queries the oracle for B. However, because the oracle machine may query the oracle a large number of times, the resulting algorithm may require more time asymptotically than either the algorithm for B or the oracle machine computing A, and may require as much space as both together. The first formal definition of relative computability, then called relative reducibility, was given by Alan Turing in 1939 in terms of oracle machines. Later in 1943 and 1952 Stephen Kleene defined an equivalent concept in terms of recursive functions. In 1944 Emil Post used the term "Turing reducibility" to refer to the concept.A polynomial-time Turing reduction is known as a Cook reduction, after Stephen Cook.".
- Turing_reduction wikiPageExternalLink whatis-davis.pdf.
- Turing_reduction wikiPageExternalLink turingredctn.html.
- Turing_reduction wikiPageID "1188375".
- Turing_reduction wikiPageLength "11079".
- Turing_reduction wikiPageOutDegree "49".
- Turing_reduction wikiPageRevisionID "677168280".
- Turing_reduction wikiPageWikiLink Alan_Turing.
- Turing_reduction wikiPageWikiLink Algorithm.
- Turing_reduction wikiPageWikiLink Arithmetical_set.
- Turing_reduction wikiPageWikiLink Category:Alan_Turing.
- Turing_reduction wikiPageWikiLink Category:Computability_theory.
- Turing_reduction wikiPageWikiLink Category:Computational_complexity_theory.
- Turing_reduction wikiPageWikiLink Church–Turing_thesis.
- Turing_reduction wikiPageWikiLink Computability_theory.
- Turing_reduction wikiPageWikiLink Computable_function.
- Turing_reduction wikiPageWikiLink Computable_set.
- Turing_reduction wikiPageWikiLink Computational_complexity_theory.
- Turing_reduction wikiPageWikiLink Constructible_universe.
- Turing_reduction wikiPageWikiLink Decision_problem.
- Turing_reduction wikiPageWikiLink Emil_Leon_Post.
- Turing_reduction wikiPageWikiLink Emil_Post.
- Turing_reduction wikiPageWikiLink Equivalence_class.
- Turing_reduction wikiPageWikiLink Function_problem.
- Turing_reduction wikiPageWikiLink Halting_problem.
- Turing_reduction wikiPageWikiLink Hyperarithmetical_hierarchy.
- Turing_reduction wikiPageWikiLink Hyperarithmetical_theory.
- Turing_reduction wikiPageWikiLink Indicator_function.
- Turing_reduction wikiPageWikiLink Log-space_reduction.
- Turing_reduction wikiPageWikiLink Many-one_reduction.
- Turing_reduction wikiPageWikiLink Mu-recursive_function.
- Turing_reduction wikiPageWikiLink Notices_of_the_American_Mathematical_Society.
- Turing_reduction wikiPageWikiLink Oracle_machine.
- Turing_reduction wikiPageWikiLink PDF.
- Turing_reduction wikiPageWikiLink P_(complexity).
- Turing_reduction wikiPageWikiLink Partial_order.
- Turing_reduction wikiPageWikiLink Partially_ordered_set.
- Turing_reduction wikiPageWikiLink Peano_arithmetic.
- Turing_reduction wikiPageWikiLink Peano_axioms.
- Turing_reduction wikiPageWikiLink Polynomial-time_reduction.
- Turing_reduction wikiPageWikiLink Portable_Document_Format.
- Turing_reduction wikiPageWikiLink Preorder.
- Turing_reduction wikiPageWikiLink Recursive_ordinal.
- Turing_reduction wikiPageWikiLink Recursive_set.
- Turing_reduction wikiPageWikiLink Recursively_enumerable_set.
- Turing_reduction wikiPageWikiLink Reduction_(complexity).
- Turing_reduction wikiPageWikiLink Smn_theorem.
- Turing_reduction wikiPageWikiLink Stephen_Cole_Kleene.
- Turing_reduction wikiPageWikiLink Stephen_Cook.
- Turing_reduction wikiPageWikiLink Stephen_Kleene.
- Turing_reduction wikiPageWikiLink Subroutine.
- Turing_reduction wikiPageWikiLink Truth-table_reduction.
- Turing_reduction wikiPageWikiLink Truth_table_reduction.
- Turing_reduction wikiPageWikiLink Turing_completeness.
- Turing_reduction wikiPageWikiLink Turing_degree.
- Turing_reduction wikiPageWikiLink Turing_jump.
- Turing_reduction wikiPageWikiLink Universal_Turing_machine.
- Turing_reduction wikiPageWikiLink Well-founded.
- Turing_reduction wikiPageWikiLink Well-founded_relation.
- Turing_reduction wikiPageWikiLink Μ-recursive_function.
- Turing_reduction wikiPageWikiLinkText "Turing equivalence".
- Turing_reduction wikiPageWikiLinkText "Turing equivalent".
- Turing_reduction wikiPageWikiLinkText "Turing reducibility".
- Turing_reduction wikiPageWikiLinkText "Turing reducible".
- Turing_reduction wikiPageWikiLinkText "Turing reduction".
- Turing_reduction wikiPageWikiLinkText "Turing".
- Turing_reduction wikiPageWikiLinkText "relative computing".
- Turing_reduction wikiPageWikiLinkText "turing reduction".
- Turing_reduction wikiPageWikiLinkText "use".
- Turing_reduction hasPhotoCollection Turing_reduction.
- Turing_reduction wikiPageUsesTemplate Template:Cite_journal.
- Turing_reduction subject Category:Alan_Turing.
- Turing_reduction subject Category:Computability_theory.
- Turing_reduction subject Category:Computational_complexity_theory.
- Turing_reduction hypernym Reduction.
- Turing_reduction type Organisation.
- Turing_reduction type Scientist.
- Turing_reduction type Scientist.
- Turing_reduction comment "In computability theory, a Turing reduction from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for B. Turing reductions can be applied to both decision problems and function problems.".
- Turing_reduction label "Turing reduction".
- Turing_reduction sameAs チューリング還元.
- Turing_reduction sameAs Transformacja_Turinga.
- Turing_reduction sameAs Redução_de_Turing.
- Turing_reduction sameAs m.04fql5.
- Turing_reduction sameAs Q4489310.
- Turing_reduction sameAs Q4489310.
- Turing_reduction wasDerivedFrom Turing_reduction?oldid=677168280.
- Turing_reduction isPrimaryTopicOf Turing_reduction.