3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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