Turing reducibility

E679186

computability-theoretic notion reducibility notion relative computability concept

Turing reducibility is a central computability-theoretic notion that compares the relative computational difficulty of decision problems by allowing one problem to be solved using an oracle for another.

Try in SPARQL Jump to: Surface forms Statements Referenced by

Observed surface forms (1)

Surface form	Occurrences
Turing reductions	1

Statements (50)

Predicate	Object
instanceOf	computability-theoretic notion ⓘ reducibility notion ⓘ relative computability concept ⓘ
allows	arbitrary adaptive oracle queries ⓘ unbounded number of oracle queries ⓘ
alsoKnownAs	Turing reducibility relation ⓘ Turing reduction NERFINISHED ⓘ
appliesTo	decision problems ⓘ sets of integers ⓘ subsets of ω ⓘ
basedOn	oracle Turing machines ⓘ
captures	relative computational difficulty ⓘ relative solvability of problems ⓘ
compares	decision problems ⓘ languages over finite alphabets ⓘ sets of natural numbers ⓘ
definition	A is Turing reducible to B if A is decidable by a Turing machine with oracle for B ⓘ
equivalenceRelation	A ≡_T B iff A ≤_T B and B ≤_T A ⓘ
field	computability theory ⓘ mathematical logic ⓘ theoretical computer science NERFINISHED ⓘ
formalCondition	A ≤_T B iff there exists an oracle Turing machine M^B that decides membership in A ⓘ
generalizes	Turing computability without oracles ⓘ many-one reducibility ⓘ
historicalPeriod	1930s ⓘ
implies	many-one reducibility implies Turing reducibility ⓘ
induces	equivalence relation of Turing equivalence ⓘ preorder on sets of natural numbers ⓘ
isWeakerThan	many-one reducibility ⓘ one-one reducibility ⓘ truth-table reducibility ⓘ
keyProperty	not antisymmetric on all sets ⓘ reflexive on all sets ⓘ transitive on all sets ⓘ
originator	Alan Turing NERFINISHED ⓘ
preserves	Turing computability ⓘ
relatedConcept	Turing degree NERFINISHED ⓘ many-one reducibility ⓘ oracle Turing machine ⓘ polynomial-time Turing reducibility ⓘ truth-table reducibility ⓘ weak truth-table reducibility ⓘ
symbol	≤_T ⓘ
usedIn	classification of unsolvable problems ⓘ degree theory ⓘ study of the analytical hierarchy ⓘ study of the arithmetical hierarchy ⓘ
usedToDefine	Turing degrees ⓘ degree of unsolvability ⓘ relative computability hierarchy ⓘ

Referenced by (2)

Full triples — surface form annotated when it differs from this entity's canonical label.

Computability Theory → fieldOfStudy → Turing reducibility ⓘ

Complexity Theory → usesConcept → Turing reducibility ⓘ

this entity surface form: Turing reductions