Login Preferences
About News Publications Statistics Downloads API Guide License How to use Preferences
bn:00325006n
Noun Concept
Categories: Reduction (complexity), Alan Turing, Articles with short description
EN
Turing reduction  A-computable  A-recursive set  Co-A-recursive set  Cook reduction
EN
In computability theory, a Turing reduction from a decision problem A {\displaystyle A} to a decision problem B {\displaystyle B} is an oracle machine which decides problem A {\displaystyle A} given an oracle for B {\displaystyle B}. Wikipedia
Definitions
Relations
Sources
EN
In computability theory, a Turing reduction from a decision problem A {\displaystyle A} to a decision problem B {\displaystyle B} is an oracle machine which decides problem A {\displaystyle A} given an oracle for B {\displaystyle B}. Wikipedia
Concept in computability theory Wikidata
A reduction that solves a problem if the solution to another problem is already known, i.e. an algorithm that could be used to solve A if it had available to it a subroutine for solving B. Wiktionary
IS A
reduction
HAS KIND
many-one reduction
NAMED AFTER
Turing
Wikipedia
EN
Turing reduction
Wikidata
EN
Turing reduction
Wiktionary
EN
Turing reduction
Wikipedia Redirections
EN
A-computable, A-recursive set, Co-A-recursive set, Cook reduction, relative computability, Turing-reducible, Turing complete (reduction), Turing complete set, Turing completeness (reduction), Turing reducibility, Turing reducible

Please note that, in order to improve your browsing experience on this website, BabelNet® uses various types of cookies, including: browsing functionality, performance and statistical cookies.

By continuing to browse the site you are agreeing to our use of cookies. OK

License