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.