Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

1 Answer

up vote 2 down vote accepted

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)$.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.