Chapter 12: Complexity ~ 357
Case 1 is taken care of by a variable Ai} and Case 2 by a variable Bu.
The variable N i will be designed in such a way that it gurantees that ID
(X,+] is one of the IDs that follows the ID (Xi'
X i +l,j can be determined from
(i) the three symbols Xi,j_], Xi). Xi,I+] above it
(ii) the move chosen by the nondeterministic TM M when one of the three
symbols (in (i» is a state.
If the state of (Xi is not Xij, X i . j - 1 or X i . j + l • then Xi+],j = XU, This is taken
care of by the variable BU'
If Xu is the state of (Xi, then X i . I + 1 is being scanned by the state Xu' The
move corresponding to the state-tape symbol pair (Xu' X i . i +]) will determine
the sequence X i + 1 • i - 1 Xi+l. j Xi+1,j+!' This is taken care of by the variable Au'
We write N i = Ai (A ii v B Ii ), where A is taken over all is, 0 :::: j :::: pen).
(i) Formulation of Bij When the state of (Xi is none of X i . i - b Xli' X i . j +].
then the transition corresponding to (Xi r-- ai+l will not affect X i . i + l • In this
case X i + l,i = Xij
Denote the tape symbols by ZI' Z:, ..., Z,. Then Xi,i-I' Xi,i and Xi,i+]
are the only tape symbols. So we ""Tite B ii as
Bij =(Yi.i-1. Zl V Yi.i-1. Z2 V ." V Yi.}-1. z) A
V Yi.j+1. z) A
C\'i,i, Z l A
Zj) V
Z2 A Yi+l.j,Z2 V '"
V (Yi,j.z,. A Yi+J,j,Z)
This first line of Bij says that Xi. H is one of the tape symbols
ZI_ Z:, . , ., Zj" The second and third lines are regarding X i . i and X i . i +]. The
fourth line says that Xli and Xi,j+1 are the same and the common value is any
one of Zj_ Z: . ..., Zj"
Recall that the head of M never moves to the left of O-cell and does not
have to move to the right of the p(n)-cell. So B io will not have the first line
and B i . jJlil will not have the third line.
(ii) Formulation of Ai} This step corresponds to the correctness of
the 2 x 3 array (see Table 12.3).
TABLE 12.3 Valid Computation
'I- - - - - , - - - - - - - - , . - - - - - - 1
I Xi )-l
X f j ,
xi )+' I
~--- - - - i - - - 1
! X,r+1,j-1
Xi+1,.)
xi+1,j+11
Case 1 is taken care of by a variable Ai} and Case 2 by a variable Bu.
The variable N i will be designed in such a way that it gurantees that ID
(X,+] is one of the IDs that follows the ID (Xi'
X i +l,j can be determined from
(i) the three symbols Xi,j_], Xi). Xi,I+] above it
(ii) the move chosen by the nondeterministic TM M when one of the three
symbols (in (i» is a state.
If the state of (Xi is not Xij, X i . j - 1 or X i . j + l • then Xi+],j = XU, This is taken
care of by the variable BU'
If Xu is the state of (Xi, then X i . I + 1 is being scanned by the state Xu' The
move corresponding to the state-tape symbol pair (Xu' X i . i +]) will determine
the sequence X i + 1 • i - 1 Xi+l. j Xi+1,j+!' This is taken care of by the variable Au'
We write N i = Ai (A ii v B Ii ), where A is taken over all is, 0 :::: j :::: pen).
(i) Formulation of Bij When the state of (Xi is none of X i . i - b Xli' X i . j +].
then the transition corresponding to (Xi r-- ai+l will not affect X i . i + l • In this
case X i + l,i = Xij
Denote the tape symbols by ZI' Z:, ..., Z,. Then Xi,i-I' Xi,i and Xi,i+]
are the only tape symbols. So we ""Tite B ii as
Bij =(Yi.i-1. Zl V Yi.i-1. Z2 V ." V Yi.}-1. z) A
V Yi.j+1. z) A
C\'i,i, Z l A
Zj) V
Z2 A Yi+l.j,Z2 V '"
V (Yi,j.z,. A Yi+J,j,Z)
This first line of Bij says that Xi. H is one of the tape symbols
ZI_ Z:, . , ., Zj" The second and third lines are regarding X i . i and X i . i +]. The
fourth line says that Xli and Xi,j+1 are the same and the common value is any
one of Zj_ Z: . ..., Zj"
Recall that the head of M never moves to the left of O-cell and does not
have to move to the right of the p(n)-cell. So B io will not have the first line
and B i . jJlil will not have the third line.
(ii) Formulation of Ai} This step corresponds to the correctness of
the 2 x 3 array (see Table 12.3).
TABLE 12.3 Valid Computation
'I- - - - - , - - - - - - - - , . - - - - - - 1
I Xi )-l
X f j ,
xi )+' I
~--- - - - i - - - 1
! X,r+1,j-1
Xi+1,.)
xi+1,j+11