356 l;! Theory of Computer Science
4. Polynomial Reduction of M to SAT
In order to check that the reduction of M to SAT is correct. we have to ensure
the correctness of
(a) the initial ID.
eb) the accepting ID. and
(c) the intermediate moves between successive IDs,
(al Simulation of initial ID
X oo must start with the initial state qo of M followed by the symbols of
H' = ala: ' .. all of length n and ending with b's (blank symbol). The
cOlTesponding boolean expression S is defined as
S = )'00'10 i\ )'Ola; /\ )'O]a, /\ ... /\ )'Olla" /\ YO,II+1-I) /\ . .. /\ YO'P(III,b
Thus given an encoding of M and 1V, we can write S in a tape of a multiple
TM M t, This takes O(p(n)) time,
(b) Simulation of accepting ID
a')II" is the accepting ID. If Pi, P:. . , ., P, are the accepting states of M, then
~Ji'" contains one of Pi' s. 1 :S i :S k in any place j. If al'ill! contains an accepting
state Pi in jth position. then
is the accepting state Pi' The corresponding
boolean expression covering all the cases (0 :S j :S pen), 1 :S i :S k) is given
by
F = F o V F] v .. , V F pinl
where
F· -
,v
1', V ... v
Each F i has k variables and hence has constant number of symbols
depending on M but not on n. The number of F;'s in F is pen). Thus given
an encoding of M and H, F can be \V11tten in O(p(n)) time on the multiple
TMM I ,
(c) Simulation of intermediate moves
We have to simulate valid moves a i r ai+], i = 0, 1, 2, '" pen).
COlTesponding to each move. \ve have to define a boolean variable N i . Hence
the entire sequence of IDs leading to acceptance of w is
N = No /\ Nt /\ ... /\ N piliH
First of all note that the symbol X i + Lj can be determined from Xi,j-lo Xij,
X i .)+] by the move (if there is one changing a i to a different ai+i)' For every
position (i, j). we have t\\70 cases:
Case 1 The state of a i is at position j.
Case 2 The state of ai is not in any of the (j - l)th, jth and (j + l)th
positions.