I'm trying to prove $U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP-complete. Showing it is NP is trivial. NP-hardness is the hard part. One way to do it would be to reduce a known NP-complete problem to $U$. Another way would be to find a general way to reduce any NP problem to $U$ in polynomial time.

I've found some online proofs for doing this. They all seem to reduce some arbitrary NP problem, say $A$, to $U$ by using the polynomial bound for the nondeterministic polynomial-time decider for $A$. So let $A$ be some NP problem, and let $N$ be its non-deterministic decider which runs in $n^{k}$ time for some $k$. Then output $\langle N, x, \#^{k} \rangle $. The issue I have with this solution is, how do you know what $k$ is? You know that $A$ is NP, so there is a non-deterministic polynomial time decider for it, but how do you know the actual degree of that polynomial? It seems false to assume it is already known, surely one should have to compute it manually to obtain a reduction. How could you compute the degree of this polynomial in polynomial time? The existing proofs seem to gloss over this critical fact.


1 Answer 1


Finding the running time of a given Turing machine is undecidable. Luckily, you don't need to find the actual degree. You only need to show the existence of a reduction from $A$ to your language, not to construct a procedure that given a description of $A\in\mathsf{NP}$ (say, as the encoding of its verifier), will output a reduction from $A$ to your language.

Think of it this way, let $\{f_n\}_{n\in\mathbb{N}}$ be a sequence of functions, where $f_i(x)=\left(M_A,x,\#^{|x|^i}\right)$. One of the functions in this sequence is the reduction you're looking for, and I don't need to point out which one (note that I can specify it in terms of the degree of the polynomial in the running time of $M_A$).

  • $\begingroup$ I don't understand why you "don't need to point out which one". When you are computing the reduction, you don't know what the degree of the polynomial is. You can't print it if you don't know what it is, so what exactly are you printing? $\endgroup$
    – user308485
    Nov 8, 2017 at 7:11
  • $\begingroup$ I don't need to print it, only to show it exists. You are looking at the proof of the existence of such a reduction. The proof even constructs one, by saying "let $d$ be the degree of the polynomial", and continuing describing the reduction in terms of the variable $d$. $\endgroup$
    – Ariel
    Nov 8, 2017 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.