[Solved]: What is the difference between these terms?

Problem Detail: 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.

Asked By : agent154

Answered By : Shaull

Let $A,Bsubseteq Sigma^*$ be languages. Many-to-one: A (computable) function $f:Sigma^*to Sigma^*$ such that $forall xin Sigma^*$, $xin Aiff 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 $Ale_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)$.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9847  Ask a Question  Download Related Notes/Documents