2
$\begingroup$

So we know that there exists a Turing Machine $M$ and a polynomial $T$ such that:

  • $M$ halts on all inputs within at most $T(|x|)$ steps
  • If $x$ is in $L$ then $M$ accepts $x$
  • If $x$ is not in $L$ then $M$ rejects $x$

We need to show that for any other problem $L'$, there exists a polynomial time computable function $f$ such that for all $x$, $f(x)$ is in $L'$ if and only if $x$ is in $L$.

I imagine the answer is simple but I'm stumped.

$\endgroup$
6
  • 1
    $\begingroup$ What have you tried? Recall that a polynomial time reduction can in itself run for a polynomial number of steps. $\endgroup$
    – Shaull
    May 28, 2013 at 9:17
  • $\begingroup$ I at first thought this was Karp reduction but now I believe this may be a Cook reduction, which is vastly different... In which case it becomes trivial. $\endgroup$
    – user8402
    May 28, 2013 at 9:38
  • 2
    $\begingroup$ Yes, it should be trivial, just don't forget that there's two trivial languages $\emptyset$ and $\Sigma^{\ast}$. $\endgroup$ May 28, 2013 at 9:42
  • $\begingroup$ Its trivial because if you know you can solve X in a polynomial number of steps then we can solve X in a polynomial number of steps + 0 calls to an Oracle for any other problem; which is the definition of Cook reducible (0 calls is a polynomial number of calls) $\endgroup$
    – user8402
    May 28, 2013 at 10:00
  • 2
    $\begingroup$ It does not seem true, because the question is not to recognize $L$ with an $L'$ oracle, it is more precise. For instance if $L'=\emptyset$ and $x\in L$, it is impossible to find an $f$ such that $f(x)\in L'$. $\endgroup$
    – Denis
    May 28, 2013 at 10:53

1 Answer 1

2
$\begingroup$

We show a karp reduction from $L$ to any other language $L'$, as long as $L'\notin\{\Sigma^*,\emptyset\}$.

The reduction proceeds as follows. Since $L'$ is non-trivial, there exists $x,y$ such that $x\in L'$ and $y\notin L'$. Given input $w$, the reduction runs $M$ on $w$ (which takes polynomial time). Then, if $w\in L$ the reduction outputs $x$, and if $w\notin L$ it outputs $y$.

Proving correctness is trivial.

As @dkuper states, this is simply not true if we allow $L'$ to be trivial. However, it is a common mistake to ignore these end-cases in exercises (which I assume this is).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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