I am currently in the process of trying to understand the original proof of NP-completeness of SAT given in the seminal paper by Cook [COOK71] and have struggled with a few of the details of the proof of Theorem 1 presented in the paper. Specifically, Cook writes:
If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, the S is P-reducible to {DNF tautologies}
Now as I understand from
suppose a non-determinisitc Turing machine M accepts S within time Q(n), where Q(n) is a polynomial. Given an input w for M, we will construct a proposition formula A(w) in conjunctive normal form such that A(w) is satisfiable iff M accepts w.
the idea of the proof is to construct (in polynomial time, i.e. polynomial length of A(w)) explicitly a prop. formula simulating the behavior of the NTM M such that A(w) in SAT iff $w \in L_M$. Now my problem is that when construcing this A(w), specifically the components concerning transition rules, Cook seems to assume a uniqe transition rule for each (state, input) combination.
(Specifically $G_{i,j}^t = \bigwedge_{s = 1}^T (\neg Q_t^i \vee \neg S_{s,t} \vee \neg P^j_{s,t} \vee Q_{t+1}^k)$ seems to assume that the state of the Turing machine at time $t+1$ is $q_k$ iff at t the turing machine was in state $q_i$ and $\sigma_j$ is read from the tape, without considering the nondeterminism of M).
Am I missing something here or is this actually an oversight in the paper?
Looking at newer versions of proofs this is either incorporated (however mostly the resulting A(w) is not explicitly given in CNF) or the proof instead uses the verifier of the NP-problem corr to M and simulates this turing machine instead. With the latter I'm wondering why this is enough to proof NP-Completness, as the existence of Karp reductions seems to require mapping M to M' not mapping the verifiers V, V' to each other at first glance.
Thanks for any clarifications!
