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.

| cite | improve this question | |
$\endgroup$
  • 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 '13 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 '13 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$ – Luke Mathieson May 28 '13 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 '13 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 '13 at 10:53
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).

| cite | improve this answer | |
$\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.