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