1
$\begingroup$

Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of $\leq$ c steps}\}$$

This question looks weird to me because itself is a TM. In general, when we say a problem is in NP, we can give an instance of that problem and using NTM to guess and verify. However, since $T_{NP}$ is a NTM, can we simply say using $T_{NP}$ itself to guess and verify in polynomial time?

Also, for the reduction part, I'm not sure but I think 3SAT is reducible to $T_{NP}$ because each clauses in 3SAT formula $\phi$ is true iff each step in $T_{NP}$ is valid.But I'm still stuck on the detail proof and argue the correctness at this moment. Any suggestion?

$\endgroup$
1
  • 1
    $\begingroup$ Your language $T_{NP}$ is not a Turing machine. It is the set of all strings $m\#w\#^c$ that satisfy some conditions. The conditions involve Turing machines. $\endgroup$ – Yuval Filmus Apr 4 '20 at 20:17
1
$\begingroup$

Let us first show that $T_{NP}$ is indeed in NP. Given an input, $m\#w\#^c$, nondeterministically guess a sequence $r$ of nondeterministic choices for $M_m$ of length $c$, simulate $M_m$ on $w$ for $c$ steps using $r$, and accept if $M_m$ accepts. This nondeterministic algorithm accepts iff $m\#w\#^c \in T_{NP}$. Furthermore, it runs in polynomial time in the input size (here it is crucial that the input contains $\#^c$ rather than $c$ encoded in binary).

To show that $T_{NP}$ is NP-hard, you can just use the definition. Suppose that $M$ is an NP machine. Then $M = M_m$ for some $m$, and $M$ runs in time $P(n)$ on an input of length $n$. Given an input $w$, map it to $m\#w\#^{P(|w|)}$. It is clear that $M_m$ accepts $w$ iff $m\#w\#^{P(|w|)} \in T_{NP}$. The reduction is polynomial since $P(n)$ is a polynomial.

$\endgroup$
2
  • $\begingroup$ Thanks for helping, it makes sense to me now. However, I'm still a bit confused about the reduction that you post. In particular, it seems you are doing self reduction instead of reducing a problem to another? $\endgroup$ – hh vh Apr 4 '20 at 20:35
  • $\begingroup$ In the second paragraph, instead of reducing from a particular problem, I show directly that any NP problem reduces to your problem. If you want a proof by reduction, simply apply my argument to some NP-complete problem of your choice. $\endgroup$ – Yuval Filmus Apr 4 '20 at 20:42

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.