# Prove a TM problem is NP-complete

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?

• 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. – Yuval Filmus Apr 4 '20 at 20:17

## 1 Answer

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.

• 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? – hh vh Apr 4 '20 at 20:35
• 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. – Yuval Filmus Apr 4 '20 at 20:42