Turing reduction is a concept in computability theory which allows for the comparison of decision problems. It involves an oracle machine that can decide problem A given an oracle for B, and can be used to produce an algorithm for A if it has access to an algorithm for B. Cook reductions are Turing reductions that run in polynomial time. The concept was first formally defined by Alan Turing in 1939.
Carnegie Mellon University
Spring 2015
A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.
No concepts data
+ 35 more concepts