Complexity Classes - Models of Computation: Exploring the Power of Computing - page 372

The instance of GENERALIZED GEOGRAPHY corresponding to an instance of AQSAT
is formed by cascading a set of diamond-shaped subgraphs, one per variable (see Fig. 8.19 ),
and connecting the bottom vertex b in the last diamond to a set of vertice s, one per clause.
An edge is drawn from a clause to a vertex associated with a literal ( x i or x i )ifthatliteral
is in the clause. The literal x i ( x i ) is associated with the middle vertex on the right-hand
(left-hand) side of a diamond. Thus, in the example, there is an edge from the leftmost
clause vertex to the left-hand vertex in the diamond for x 3 and to the right-hand vertices in
diamonds for x 1 and x 2 .
Let the geography game be played on this graph starting with the first player from the
topmost vertex labeled t . The first player can choose either the left or right path. The second
player has only one choice, taking it to the bottom of the first diamond, and the first player
now has only one choice, taking it to the top of the second diamond. The second player
now can choose a path to follow. Continuing in this fashion, we see that the first (second)
player can exercise a choice on the odd- (even-) numbered diamonds counting from the top.
Since the number of quantifiers is even, the choice at the bottom vertex labeled b belongs to
the second player. Observe that whatever choices are made within the diamonds, the vertices
labeled m and b are visited.
Because the goal of each player is to force the other player into a position from which
it has no moves, at vertex b the second player attempts to choose a clause vertex such that
the first player has no moves: that is, every vertex reachable from the clause vertex chosen by
the second player has already been visited. On the other hand, if all clauses are satisfiable,
then for every clause chosen by the second player there should be an edge from its vertex to
a diamond vertex that has not been previously visited. To insure that the first player wins if
and only if the instance of AQSAT used to construct this graph is a “Yes” instance, the first
player always cho os es an edge according to the directions in Fig. 8.19 . For example, it visits
the vertex labeled x 1 if it wishes to set x 1 = 1 because this means that the vertex labeled x 1
is not visited on the path from t to b and can be visited by the first player on the last step of
the game. Since each vertex labeled m and b is visited before a clause vertex is visited, the
second player does not have a move and loses.
8.13 The Circuit Model of Computation
The complexity classes seen so far in this chapter are defined in terms of the space and
time needed to recognize languages with deterministic and nondeterministic Turing machines.
These classes generally help us to understand the complexity of serial computation. Circuit
complexity classes, studied in this section, help us to understand parallel computation.
Since a circuit is a fixed interconnection of gates, each circuit computes a single Boolean
function on a fixed number of inputs. Thus, to compute the unbounded set of functions
computed by a Turing machine, a family of circuits is needed. In this section we investigate
uniform and non-uniform circuit families. A uniform family of circuits is a potentially un-
bounded set of circuits for which there is a Turing machine that, given an integer n in unary
notation, writes a description of the n th circuit. We show that uniform circuits compute the
samefunctionsasTuringmachines.
As mentioned below, non-uniform families of circuits are so powerful that they can com-
pute functions not computed by Turing machines. Given the Church-Turing thesis, it doesn't
make sense to assume non-uniform circuits as a model of computation. On the other hand, if