2
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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". $\endgroup$
    – Ayrat
    Commented Nov 29, 2021 at 9:31
  • $\begingroup$ @Ayrat, for what it's worth, I thought it was a perfectly reasonable question. The difference between constructive vs non-constructive proofs is tricky, especially in computer science, where our intuition usually goes to constructive arguments. $\endgroup$
    – D.W. ♦
    Commented Nov 29, 2021 at 9:55

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.