Prove a TM problem is NP-complete

Question

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?

Answer 1

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.