# Why proofs of Cook's Theorem assume k is given (n^k for NTM)?

A typical proof of Cook-Levin's Theorem proceeds like this:

Suppose problem X is in NP. Then there is an NTM M deciding X in time n^k, for some k. Given a word w, NTM M, and k, we construct a Boolean formula φ in polytime(|w|) that is satisfiable iff the NTM accepts w, as follows. [...]

Question: why can we assume that k is given? I agree that "there exists such k", however knowing that it exists and directly using it in the reduction are different things (to me). I would expect the reduction to be independent of k (so the formula doesn't depend on k), but the proof of its correctness relies on the fact that k in N exists.

Look at the statement of Cook's theorem: it states that for any problem in NP, there exists a reduction from that problem to 3SAT. The key part is the "there exists". The proof only needs to show that there exists such a reduction. For these purposes, it suffices to note that there exists a $$k$$ such that $$M$$ runs in time $$O(n^k)$$. There is no requirement that we be able to find $$k$$ or find the reduction.
• Unexpected! Thanks. For the same reason I should have asked why the reduction depends on the NTM M, making the question even more silly, and the answer is the same: "suffice to show there exists". Commented Nov 29, 2021 at 9:31