Chapter 12: Complexity J;;l 355
If M accepts an input 11' and I}v I= n. then there exists a sequence of moves
of M such that
1. O'{! is the initial ID of M with input w.
2. 0"0 ~ at ~ ... ~ (XI;, k ::; pen).
3. al; is an ID with an accepting state.
4. Each (Xi is a string of nonblanks, its leftmost symbol being the
leftmost symbol of w (the only exception occurs when the processing
of w is complete, in which case the ID is qb).
2. Representation of Sequence of Moves of M
As the maximum number of steps on w is pen) we need not bother about the
contents beyond pen) cells. We can write ai as a sequence of pen) + 1 symbols
(one symbol for the state and the remaining symbols for the tape symbols).
So Gi = XiOX il ... Xi, p(Il)'
By assuming Q n r = 0, we can locate the state in ai and hence the
position of the tape head. The length of some ID may be less than pen). In
this case we pad the ID on the right with blank symbols. so that all IDs are
of the same length pen) + 1. Also the acceptance may happen earlier. If a lll
is an accepting ID in the course of processing 11', then we write O'{! 1- ... fa;;! f- all! ... f- am = ai.pU/I·
Thus all IDs have pen) + 1 symbols and any computation has pen) moves.
TABLE 12.2 Array of IDs
ID
0
Ct.o
.'1'00
.'1'01
Ct.,
.'1'10
.'1',1
Ct.,
.'1"0
X"
Ui+l
X", 0
Xi+1 1
Cf.,D(ni
j - 1
X,j-1
Xj+1,j-1
j
j + 1
pen)
So we can represent any computation as an (p(n) +1) X (p(n) + 1) alTay
as in Table 12.2.
3. Representation of IDs in Terms of Boolean Variables
We define a boolean variable
conesponding to ii, j)th entry in the ith ID.
The variable YiiA represents the proposition that
=A. where A is a state or
tape symbol and 0 ::; i, j :; pen).
We simulate the sequence of IDs leading to the acceptance of an input
string w by a boolean expression. This is done in such a way that M accepts
1\' if an only if the simulated boolean expression E l1 .\! is satisfiable.