1
$\begingroup$

I am reviewing things I learned, and I can't suddenly come up with an example of reduction that is not many-one, but Turing reduction. Can anyone present such an example?

$\endgroup$
1
  • 2
    $\begingroup$ Your title asks for a reduction that is not many-one and not Turing, but the question asks for something that is not many-one and is Turing. Which do you want? $\endgroup$ Nov 22 '14 at 21:08
2
$\begingroup$

A simple example would be a reduction from e.g. $SAT$ to it's complement $\overline{SAT}$, which works as follows: given a formula $\varphi$, you can decide whether $\varphi$ is satisfiable by deciding whether $\varphi\in \overline{SAT}$, and then negating the answer. This is a Turing reduction, since you use an oracle for $\overline{SAT}$ to solve $SAT$.

A similar example can be constructed for HALT and it's complement, if you want decidability, rather than complexity.

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