Question

13. Show that U-{(M, z, #t1 NTM M accepts x within t steps on at least one branch) is NP-complete. Note that I really like this question.

Answer 1

In NP:

To show U is in NP, we need to show the existence of a TM (Turing Machine) M' accepting U in polynomial time. Basically M' plays the role of M except that it treats the middle part x as its input , and M' uses #^t to keep track of the number of steps it perform.

M' accepts (M,x,#^t) in polynomial time if M accepts x in t time.

(Also you can use the following way to see U is NP)

To see why U is NP-complete, let A be any language in NP. Since A is in NP, there exists an NTM N_A that accepts any stringy in A within |y|k steps, for some k.Then, we can reduce A to U as follows: Given any input stringy, we set M=NA,x=y and t=k;immediately, we have y in A if and only if〈M, x,#t〉in U. As the reduction is polynomial time, we have shown that any language in NP is polynomial time reducible to U. As U is in NP, so by definition U is NP-complete.

In NP-hard:

Let M be a polynomial time NTM (Nondeterministic Turing Machine) with time bound p(n). let U_M,p(n) be the language accepted by such a TM. consider the following reduction from U_M,p(n) to U - { (M,x,#^p(n)) | NTM M accepts x within t steps on at least one branch }. Clearly $x \in$ U_M,p(n) if (M,x,#^p(n)) $\in$ U.