P Langauage to NP Reduction in Polynomial Time

130 Views Asked by At

Let L be a language in P. Prove it is polynomial time reducible to any language in NP, including any language in P, which contains at least one string but doesn’t contain all the strings.

I tried solving this, One solution I can think of is making a deterministic Turing machine that recognizes the problem P in polynomial time and then I can convert the Turing machine into a non-deterministic machine but that will that exponential time. Can we do a conversion in polynomial time?

1

There are 1 best solutions below

0
On

A deterministic Turing machine is also (trivially) a non deterministic Turing machine. No particular transformation is needed.

I would also add that your target language need not be in $\mathsf{NP}$. It can be any non-trivial language $L'$, where non-trivial means $\emptyset \subsetneq L' \subsetneq \Sigma^\star$ for a fixed alphabet $\Sigma$.

Indeed, the following holds: If $L\in \mathsf{P}$ and $\emptyset \subsetneq L' \subsetneq \Sigma^\star$, then $L\leq^p_m L'$.

To see why, let $y,z$ be two strings such that $y\in L'$ and $z\notin L'$ (this is where we use the fact that $L'$ is non-trivial), and let $f$ be the following function: $$f(x) = \left\{ \begin{align} y & \text{, if $x\in L$} \\ z & \text{, if $x\notin L$} \end{align} \right.$$ Now, $f$ is clearly computable in polynomial time because $x\in L$ can be decided in polynomial time. Moreover, $x\in L \Leftrightarrow f(x)\in L'$, so the definition of $L\leq^p_m L'$ is satisfied.