4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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