Unclear Passage in Cook's Proof of SAT NP-Completeness: Why The Machine M Should Be Modified?

44 Views Asked by At

I am studying Cook's seminal 1971 paper, in particular the proof of Theorem 1 that is now known to state that every NP problem is reducible to CIRCUIT-SAT in polynomial time.

Does anyone know why Cook states at the bottom of the left column on page 153 that, "The machine $M$ should be modified so that it continues to compute in some trivial fashion after reaching an accepting state, so that $A(w)$ will be satisfied" ?

Specifically, I fail to understand the particular case that Cook had in mind to necessitate the statement. If I do not modify $M$ in any way, then $M$ will enter an accepting state at step $T$ because Cook states in the beginning of the proof that, "there is a computation of $M$ with input $w$ that ends in an accepting state within $T = Q(n)$ steps". At step $T$, I see that clause $B$, $C$, $D$, $E$, and $I$ are satisfied. The only possibility that necessitated Cook to make the statement in question is then clause $F$, $G$, and $H$ at step $T$ because Cook states, "$F$, $G$, and $H$ assert that for each time $t$ the values of the $P$'s, $Q$'s and $S$'s are updated properly. For example, $G$ is the conjunction over all $t$, $i$, $j$ of $G^t_{i,j}$".

Substituting $T$ to the formula of $G^t_{i,j}$ given in the paper gives $\wedge_{s=1}^T (\neg Q_{T}^i \vee \neg S_{s,T} \vee \neg P_{s,T}^j \vee Q_{T+1}^k)$. So, I suspect that "to compute in some trivial fashion after reaching an accepting state" at step $T$ is to have $Q_{T+1}^k$ defined. But, since $M$ halts at step $T$, this means that $M$ has no transition that starts at $q_i$ in the first place, and therefore, $Q_{T}^i$ is always false and $G^T_{i,j}$ will be true even when $Q_{T+1}^k$ is always set to false in the construction. So, I fail to see why Cook needs to give the statement that "the machine $M$ should be modified so that it continues to compute in some trivial fashion after reaching an accepting state, so that $A(w)$ will be satisfied" because as I explained, $A(w)$ is satisfied when $M$ reaches an accepting state without modifying $M$. What particular case did Cook had in mind then for giving the statement in question?

1

There are 1 best solutions below

0
On BEST ANSWER

Note that it's within $T$ steps, not at exactly $T$ steps. An accepting computation may actually take fewer than $T$ steps, but we still need to give definite values to the variables describing the state, head location, and tape contents at all later steps, in order to satisfy clauses $B$, $C$, and $D$. Cook solves that trivial problem by modifying the machine in a trivial way.