To show that any language $L \in NP$ is many one reducible to HP

Question

Question : To show that any language $L \in NP$ is many one reducible to HP.

Let $L$ be a language in NP, it means there exist a non-deterministic Turing machine for $L$. Let $x$ be a input string to this non-deterministic Turing machine, now I have come up with $f(x)$ such that $x \in L \equiv f(x) \in $HP and $f$ should be computable function. $f$ will be a function which takes $x$ string as an input and gives $M.y$(. means concatenation) as output, where $M$ the encoding of an Turing machine and $y$ is just a string.

Answer 1

In fact we can prove something a bit stronger: any language $L$ in NP is polynomial-time reducible to the Halting Problem $HP$.

So let $L$ be a language in NP. We have a nondeterministic TM $N$ for $L$, which runs in polynomial time. So $$ x \in L \iff N \text{ accepts } x $$ Now $N$ runs in polynomial time --- let's say that on input of size $n$ it runs in time $P(n)$, where $P$ is a polynomial. Here is an algorithm reducing $L$ to $HP$:

• On input string $x$, construct a Turing Machine $M_{x}$ which does the following: "Write $x$ on the input tape, then start trying all possible runs of $N$ on input $x$, in increasing order of size (first try runs of length 0, then runs of length 1, and so on). If a run ever accepts, then halt. otherwise keep running forever.

Now if $x \in L$ then there will be a run of $N$ on input $x$ that accepts, so $M_x$ will halt. And if $x \notin L$, then no runs of $N$ on input $x$ will accept, so $M_x$ will run forever. Thus, $$ x \mapsto M_x $$ is a reduction from $L$ to $HP$. And you may also want to check that the reduction runs in linear time. (That is, the amount of time required to construct $M_x$ from $x$ is linear in $x$.)

Answer 2

The language $HP$ contains all pairs $\langle M, w \rangle$ such that $M$ halts on $w$. You are told that $L$ is accepted by a NDTM meaning that there is a deterministic TM $M_L$ accepting the same language $L$. You modify $M_L$ so that when $M_L$ rejects $w$ it loops infinitely. Call it $M'_L$. Thus, given input $w$, your function $f$ should create a pair $\langle M'_L, w \rangle$ which means that $w \in L$ iff $M'_L$ halts on $w$ iff $\langle M'_L, w \rangle \in HP$.