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,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)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9847
0 comments:
Post a Comment
Let us know your responses and feedback