# Prove that if a problem L can be decided in polynomial time, then L ≤p L' for any other problem L'

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.

• What have you tried? Recall that a polynomial time reduction can in itself run for a polynomial number of steps. – Shaull May 28 '13 at 9:17
• 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. – user8402 May 28 '13 at 9:38
• Yes, it should be trivial, just don't forget that there's two trivial languages $\emptyset$ and $\Sigma^{\ast}$. – Luke Mathieson May 28 '13 at 9:42
• 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) – user8402 May 28 '13 at 10:00
• 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'$. – Denis May 28 '13 at 10:53

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