# What is the difference between these terms?

Between my textbook and various online sources (namely wikipedia), I'm very confused... can somebody clear up which words are synonymous and which mean different things?

• Many-to-one reduction
• Mapping reduction
• Turing reduction
• Cook reduction
• Karp reduction
• Polynomial-time many-to-one reduction
• Polynomial time turing reduction

I've also seen others, but I can't recall them currently.

-
Have you read the definitions? What do they say? I am sure they use different words/formulae; why do you think they mean the same things? –  Raphael Feb 17 '13 at 8:54
@Raphael My textbook talks about mapping reductions. Wikipedia (in the articles I've looked at) uses many-to-one and mapping and Turing reductions... I don't know if they're different words used with the same meaning, or if they actually mean something different. –  agent154 Feb 18 '13 at 2:02
If either source does not define the notions they use, ignore them. Stick to those that have definitions, which you can then compare. –  Raphael Feb 18 '13 at 8:49

Let $A,B\subseteq \Sigma^*$ be languages.

Many-to-one: A (computable) function $f:\Sigma^*\to \Sigma^*$ such that $\forall x\in \Sigma^*$, $x\in A\iff f(x)\in B$. The names "Mapping reduction" and "Karp reductions", to my knowledge, refer to "Many to one". The "Many to one" means that $f$ may not be injective.

Turing reduction: we say that $A\le_T B$ if, given an oracle to the language $B$, we can use it to solve $A$. The word "solve" here should be in the context of a specific complexity/computability class.

Turing reductions are weaker than many-to-one reductions. The latter can be viewed as Turing reductions where we are only allowed to call the oracle once - at the very end of the run.

polynomial time many-to-one reductions - simply adding a constraint that the reduction $f$ is computable in polynomial time.

polynomial time Turing reduction (= Cook reduction) - add the constraint that the oracle machine runs in polynomial time, counting each oracle call as $O(1)$.

-