Consequently, the problem is in NP . For the purpose of the proof consider any problem K in NP . The Structure of E x The Boolean expression E x describes how an accepting computation of M on input x should look. E init states that C 0 is an initial configuration. E rule 1 E rule t states that an accepting computation uses a sequence of t transition rules.
E accept states that the last transition rule in enters an accepting state.
The Variables of E x The Boolean expression E x uses variables of the form w i,r,j,X and variables of the form w i, . Each variable provides a statement about a possible property of an accepting computation. An assignment that satisfies E x provides the value 1 to those variables whose statements hold for the computation in question, and provides the value 0 to those variables whose statements do not hold for that computation. The expression E conf i is the conjunction of the following Boolean expressions. This expression states that each entry in the input segment has at most one symbol.