3.6

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Theorem 3.28

Proof

A number of two-person games have been shown to be PSPACE-complete. Indeed, the alternating quantifier characterization of Corollary 3.20 suggests that every problem in PSPACE may be viewed as a two-person game. For instance, the problem QBF may be viewed as a game played between two players $c03-math-1509$ and $c03-math-1510$ . Without loss of generality, we may assume that a given QBF F has alternating quantifiers in its normal form:

where $c03-math-1513$ if m is odd, $c03-math-1515$ if m is even, and F₁ is an unquantified Boolean formula over variables $c03-math-1518$ . For any Boolean formula not of this form, we can insert a quantifier over a dummy variable between any two consecutive quantifiers of the same type to convert it to an equivalent formula of this form. On such a formula F, player $c03-math-1520$ tries to prove that F is true and player $c03-math-1522$ works as an adversary trying to prove that F is false (see Exercise 3.12). When the problem QBF is presented as a game, the notion of the player $c03-math-1524$ having a winning strategy is equivalent to the notion of F being true. Thus, the game QBF is PSPACE-complete.

**Figure 3.2** (a) The digraphs H_i and K_i. (b) An example of digraph H.

In the following, we show a natural two-person game GEOGRAPHY to be PSPACE-complete. A game configuration of GEOGRAPHY is a directed graph $c03-math-1526$ with a starting node $c03-math-1527$ explicitly marked. There is a move from $c03-math-1528$ to $c03-math-1529$ (i.e., $c03-math-1530$ ) if H₂ is the subgraph of H₁ with the node v₁ removed, and $c03-math-1534$ is an edge of H₁. In other words, the players, starting with an initial graph H and a starting node v, take turns to visit one of the unvisited neighbors of the current node until one of the players reaches a node of which all the neighbors have been visited.

GEOGRAPHY: Given a digraph H with a marked node v, determine whether the next player has a winning strategy.

Theorem 3.29

Proof

It is easy to see that GEOGRAPHY is a polynomially bounded game, and so, by Theorem 3.28, it is in PSPACE. To see that GEOGRAPHY is PSPACE-complete, we reduce the problem 3-QBF to it. Let F be a 3-CNF quantified formula of the form

where each C_i, $c03-math-1543$ , is a clause of three literals. (As we discussed above, we may assume that the quantifiers in F alternate between $c03-math-1545$ and $c03-math-1546$ .) For each variable x_i (and y_i), $c03-math-1549$ , we let H_i (and, respectively, K_i) be a four-node digraph shown in Figure 3.2(a). The graph H consists of

graphs $c03-math-1553$ , concatenated with edges $c03-math-1554$ , for $c03-math-1555$ , and $c03-math-1556$ , for $c03-math-1557$ ;
m new nodes $c03-math-1559$ together with the new edges $c03-math-1560$ , for $c03-math-1561$ ; and
for each clause $c03-math-1562$ , $c03-math-1563$ , three edges $c03-math-1564$ , $c03-math-1565$ .

Figure 3.2(b) shows the graph H for formula $c03-math-1567$ . Finally, we let u₁ be the starting node.

We claim that there is a winning strategy on the game configuration $c03-math-1572$ of GEOGRAPHY if and only if F is true. Let us observe how the game can be played. Assume that the first player is player 0. First, in the first $c03-math-1574$ moves, the two players are forced to visit from node u₁ to node z_n, with player 0 at the $c03-math-1577$ th move visiting either node x_i or node $c03-math-1579$ and the player 1 at the $c03-math-1580$ th move visiting either node y_i or $c03-math-1582$ . When these moves are made, the resulting graph H^′ contains only the nodes z_n, $c03-math-1585$ and one node from each pair $c03-math-1586$ and $c03-math-1587$ , $c03-math-1588$ . At this point, it is player 1's turn. Player 0 can win if and only if for any move from z_n to any c_j, $c03-math-1591$ , played by player 1, player 0 can find a move from c_j to some ℓ_j,k, $c03-math-1594$ , in $c03-math-1595$ .

Now we may define an assignment τ on $c03-math-1597$ according to the first $c03-math-1598$ moves on $c03-math-1599$ (i.e., let $c03-math-1600$ if and only if $c03-math-1601$ and $c03-math-1602$ if and only if $c03-math-1603$ ) and then $c03-math-1604$ is true to τ if and only if player 0wins after $c03-math-1606$ moves. Thus, player 0 has a winning strategy on $c03-math-1607$ if and only if

if and only if

if and only if F is true.

3.6 EXP-Complete Problems

All complete problems studied so far are candidates for intractable problems, but their intractability still depends on the separation of the classes NP, PSPACE, and PH from the class P. Are there natural problems that are provably intractable in the sense that they can be proved not belonging to P? In this section, we present a few problems that are complete for EXP and, hence,

Our first EXP-complete problem is the bounded halting problem on deterministic machines with the time bound encoded in binary form.

EXPONENTIAL-TIME BOUNDED HALTING PROBLEM (EXP-BHP): Given a DTM M, a string x, and an integer n > 0, written in the binary form, determine whether M(x) halts in n moves.

Proposition 3.30

Proof

We note that in the above problem, if the time bound n is written in the unary form (as in the problem BHP), then the problem becomes polynomial-time solvable. Indeed, there is a simple translation of most P-complete problems¹ to EXP-complete problems by more succinct encodings of the inputs. In the following, we demonstrate this idea on the famous P-complete problem, CIRCUIT VALUE PROBLEM (CVP).

Let C be a Boolean circuit² satisfying the following property: C has n gates numbered from 1 to n; we let C(i) denote the gate of C numbered i. There are four types of gates in circuit C: ZERO gates, ONE gates, AND gates, and OR gates. A ZERO (ONE) gate has no input and one output whose value is 0 (1, respectively). An AND (OR) gate has two inputs and one output whose value is the Boolean product (Boolean sum, respectively) of the two inputs. If the gate i is an AND or OR gate, then its two inputs are the outputs of two gates whose numbers are lower than i. Note that this circuit C does not have input gates and so it computes a unique Boolean value (the output of gate n). If the circuit is given explicitly, then its output value is computable in polynomial time. (In fact, it is P-complete; see Theorem 6.41). In the following, we consider the encoding of the circuit by a DTM. We say that a DTM M generates a circuit C of size n in time m if for all i, $c03-math-1645$ , M(i) outputs a triple $c03-math-1647$ in m moves, with $c03-math-1649$ and $c03-math-1650$ if b ≤ 1, such that

If b = 0, then $c03-math-1653$ ;
If b = 1, then $c03-math-1655$ ;
If b = 2, then $c03-math-1657$ ;
If b = 3, then $c03-math-1659$ .

EXPONENTIAL-SIZE CIRCUIT VALUE PROBLEM (EXP-CVP): Given a DTM M; an integer t > 0, written in the unary form 0^t; and an integer s > 0, written in the binary form, such that M generates a circuit C of size s in time t, determine whether circuit C outputs 1.

Theorem 3.31

Proof

It is easy to see that EXP-CVP is in EXP. For each input $c03-math-1669$ , the circuit C generated by M has size s and we can write down the whole circuit C in $c03-math-1674$ moves. Then, we can simulate the circuit in time polynomial in s.

To see that EXP-CVP is complete for EXP, assume that $c03-math-1676$ is a DTM with runtime bounded by 2^cn for some constant c > 0. Let $c03-math-1679$ . Then, for any input w of length n, there is a unique sequence of configurations α₀, α₁, $c03-math-1684$ , α_m such that

Each α_i, $c03-math-1687$ , is of length $c03-math-1688$ ;
$c03-math-1689$ , for each $c03-math-1690$ ;
α₀ is the initial configuration of M(w); and
α_m is in an accepting state if and only if $c03-math-1694$ .

As in Cook's theorem, we may define a set of Boolean variables $c03-math-1695$ to encode this sequence of configurations. To be more precise, we define a circuit C that contains gates named $c03-math-1697$ , for all $c03-math-1698$ , $c03-math-1699$ , and $c03-math-1700$ , plus someauxiliary gates, so that the output of gate $c03-math-1701$ is 1 if and only if the jth character of α_i is a. To satisfy this condition, we let gates $c03-math-1705$ be constant gates corresponding to the initial configuration α₀. For each i ≥ 1 and each $c03-math-1708$ , $c03-math-1709$ , we define a subcircuit $c03-math-1710$ , whose output gate is $c03-math-1711$ and input gates are $c03-math-1712$ , $c03-math-1713$ , $c03-math-1714$ . This subcircuit is defined from the transition function δ of M, just as in the Boolean formula ϕ₄ of Cook's theorem. We assume that M has a unique accepting configuration $c03-math-1719$ , and we let $c03-math-1720$ be the output gate of C. Then, it is clear that the output of circuit C is 1 if and only if M accepts w. Furthermore, the size of circuit C is polynomial in m.

Now, we observe that the circuit C can be encoded into a DTM M_C that generates it in time polynomial in $c03-math-1729$ . This is true because each subcircuit $c03-math-1730$ , i ≥ 1, has a constant size and its structure depends only on the transition function δ of M (e.g., for a fixed a, $c03-math-1735$ and $c03-math-1736$ are identical except for the input gates), and so it can be generated by M_C using a table look-up method, and the runtime on each gate is polynomial in n. (Note that the length of the binary expansion of the integer i is linear in n.) In addition, the value of each constant gate $c03-math-1741$ can be determined from input w only and so can be generated in time linear in n. Thus, circuit C can be generated by M_C in time polynomial in n, and the codes of M_C itself is easily computed from M and w. (See Exercise 3.16 for more discussions.) It follows that the reduction from L(M) to EXP-CVP can be done in polynomial time.

In Section 3.5, we have shown that a polynomially boundedtwo-person game is solvable in PSPACE and that some natural games, such as GEOGRAPHY, are PSPACE-complete. In the following, we consider a game that is not polynomially bounded and show that it is complete for the class EXP.

Informally, the BOOLEAN FORMULA GAME (BFG) is a two-person game played on a Boolean formula F. The variables of the formula F are partitioned into three subsets: X, Y, and {t}. The game begins with an initial assignment τ₀ on variables in $c03-math-1757$ such that F evaluates to 1 under τ₀. The two players 0 and 1 take turns to change the assignment to variables, subject to the following rules:

Player 0 must assign value 1 to the variable t and must not change the Boolean value of any variable $c03-math-1761$ .
Player 1 must assign value 0 to the variable t and must not change the Boolean value of any variable $c03-math-1763$ .

A player loses if the formula F becomes 0 after his/her move.

We notice that a Boolean formula F of m variables has 2^m different assignments for its variables and, hence, this game is not polynomially bounded. In fact, the game may last forever, with two players repeating the same assignments. It is easy to see, nevertheless, that these repeated moves can be identified and ignored as far as the winning strategy is concerned.

In the following formal definition of the game BFG, we write $c03-math-1768$ to denote a Boolean function with its variables partitioned into three sets A, B, and C. Now we define, following the notation of the last section, $c03-math-1772$ , where

BOOLEAN FORMULA GAME (BFG): Given a Boolean formula $c03-math-1774$ and a truth assignment $c03-math-1775$ such that $c03-math-1776$ , determine whether the player 0 has a winning strategy on the game configuration $c03-math-1777$ .

Theorem 3.32

Proof

Our proof is based on the ATM characterization of the class EXP. Recall that we proved in Theorem 3.21 that $c03-math-1778$ . To see that $c03-math-1779$ , we describe an alternating tree T for input $c03-math-1781$ as follows:

The root of T is an existential node with the name $c03-math-1783$ .
For each existential node v of T, with the name $c03-math-1786$ , let $c03-math-1787$ , $c03-math-1788$ , $c03-math-1789$ . If $c03-math-1790$ , then v is a leaf. Otherwise, node v has $c03-math-1793$ children, each a universal node with a unique name $c03-math-1794$ , $c03-math-1795$ .
For each universal node v of T, with the name $c03-math-1798$ , let $c03-math-1799$ , $c03-math-1800$ , $c03-math-1801$ . If $c03-math-1802$ , then v is a leaf with label ACCEPT. Otherwise, node v has $c03-math-1805$ children, each an existential node with a unique name $c03-math-1806$ , $c03-math-1807$ .

It is obvious that this tree can be simulated by an ATM M in linear space. Furthermore, M accepts input $c03-math-1810$ if and only if $c03-math-1811$ .

Next, we show that each set $c03-math-1812$ is $c03-math-1813$ -reducible to BFG and, hence, BFG is EXP-complete. Assume that $c03-math-1814$ . Then, by Theorem 3.21, there is an ATM $c03-math-1815$ accepting A in space cn for some constant c > 0. That is, on input w, each configuration of the computation tree of M on w has length at most $c03-math-1822$ . We pad the short configurations with extra blanks and assume that every configuration has a uniform length $c03-math-1823$ . For our proof below, we further assume the following settings:

The initial configuration of M(w) is in an existential state; and
All children of an existential configuration are universal configurations, and all children of a universal configuration are existential configurations.

It is left to the reader to check that a linear space ATM can be easily modified into an equivalent linear space ATM having the above properties.

As in Cook's theorem, we define Boolean variables to encode the configurations of the ATM M on input w. We let $c03-math-1827$ and $c03-math-1828$ , where $c03-math-1829$ . The intended interpretation of the above variables is, as in Cook's theorem, that $c03-math-1830$ if and only if the ithcharacter of the configuration β is a and $c03-math-1834$ if and only if the ith character of the configuration α is a, where α and β are two configurations of the computation tree of M(w). Based on this interpretation, we define a formula F_w to denote the following properties on the configurations α and β (we say β is a rejecting configuration if it is a halting configuration but is not in an accepting state):

If $c03-math-1845$ , then $c03-math-1846$ and β is not a rejecting configuration; and
If $c03-math-1848$ , then $c03-math-1849$ and α is not in an accepting state.

To do so, we let ϕ₁ be the Boolean formula that asserts that α and β are indeed configurations of M. To be more precise, we let $c03-math-1855$ , where $c03-math-1856$ asserts that for each i, $c03-math-1858$ , there is a unique $c03-math-1859$ , such that $c03-math-1860$ ; $c03-math-1861$ asserts that for each i, $c03-math-1863$ , there is a unique $c03-math-1864$ , such that $c03-math-1865$ ; $c03-math-1866$ asserts that there is a unique i, $c03-math-1868$ , such that $c03-math-1869$ for some $c03-math-1870$ ; and $c03-math-1871$ asserts that there is a unique i, $c03-math-1873$ , such that $c03-math-1874$ for some $c03-math-1875$ . The formulas $c03-math-1876$ and $c03-math-1877$ are just like formula ϕ₁ in Cook's theorem. Formulas $c03-math-1879$ and $c03-math-1880$ can be similarly defined. For instance, we can define $c03-math-1881$ by

Next, let ϕ₂ be the formula for the property $c03-math-1884$ and ϕ₃ be the formula for the property $c03-math-1886$ . Again, they can be defined as in Cook's theorem. Finally, let ϕ₄ denote the property that β is not a rejecting configuration and ϕ₅ denote the property that α is not in an accepting state. These are also easy to define:

where $c03-math-1892$ and $c03-math-1893$ .

Using these components, we define

We also define an initial assignment τ₀ as follows: For each i, $c03-math-1897$ , and each $c03-math-1898$ , $c03-math-1899$ if and only if the ith character of the initial configuration of M(w) is a and $c03-math-1903$ .

Assume that $c03-math-1904$ is a game configuration for BFG. If the assignment τ on variables in Y defines an existential configuration α of M(w) (based on the above interpretation of the variables $c03-math-1909$ ) and the player 0 is to make the next move, then the only moves he/she can make are to define an assignment $c03-math-1910$ on variables in X such that, with respect to $c03-math-1912$ , β is a successor of α. After that, the only moves player 1 can make are to make α a successor of β. Thus, starting with τ₀ that defines α to be the initial configuration of M(w), the sequence of moves made by the two players is a path of the computation tree of M(w). At the end of the path, the player 0 cannot move (and loses) if all next moves in the computation tree of M(w) reject and the player 1 loses if all next moves accept. This shows that the game tree of BFG on $c03-math-1922$ coincides with the computation tree of M(w), and we conclude that the player 0 has a winning strategy on $c03-math-1924$ if and only if M accepts w.

In the above, we have demonstrated some complete problems for the class EXP. In addition to these problems, there are problems that are known to have even higher complexity, for instance, complete for the classes NEXP, EXPSPACE, and so on. In the following, we list a few of these complete problems and leave their proofs asexercises.

First, using the technique of succinct encoding for the problem EXP-CVP, we can encode a Boolean formula of exponential size in a DTM and the corresponding satisfiability problem becomes NEXP-complete. We say a 3-CNF formula is of size (n,m) if it has n Boolean variables and m clauses. We say that a DTM M generates a 3-CNF formula F of size (n,m) in time t if for any $c03-math-1934$ , M(j) outputs in t moves a 6-tuple $c03-math-1937$ , with $c03-math-1938$ and $c03-math-1939$ , such that (i) the three variables occurring in clause C_j are $c03-math-1941$ and (ii) for each $c03-math-1942$ , $c03-math-1943$ occurs in C_j positively if and only if $c03-math-1945$ .

EXP-SAT: Given a DTM M, integers n,m written in the binary form, and an integer t in unary form, such that M generates a 3-CNF formula F of size (n,m) in time t, determine whether F is satisfiable.

Theorem 3.33

In Theorem 3.27, we showed that the problem of determining the totality of a given regular expression (TRE) is PSPACE-complete. The idea of the proof is that regular expressions can be used to encode computation paths of a DTM in such a way that a computation path of length exponential in n can be encoded by a regular expression of length polynomial in n. We say a string is an extended regular expression if it is a regular expression with an additional intersection operation $c03-math-1956$ . For any two languages A and B, $c03-math-1959$ simply denotes the set intersection of A and B. The following result indicates that even more succinct representations of a computation path of a DTM can be achieved by extended regular expressions.

TOTALITY OF EXTENDED REGULAR EXPRESSION (TERE): Given an extended regular expression R over set Σ, determine whether $c03-math-1964$ .

Theorem 3.34

Exercises

3.1 We say set A is strong-NP reducible to set B ( $c03-math-1967$ ) if there is a polynomial-time oracle NTM M such that for each x, at least one computation path of $c03-math-1971$ halts in an accepting state, and all computation paths of $c03-math-1972$ halting in an accepting state output value 1 if $c03-math-1973$ , and all such paths output value 0 if $c03-math-1974$ .

Prove that $c03-math-1975$ is indeed a reducibility (i.e., it satisfies the transitivity property).
Prove that $c03-math-1976$ if and only if [ $c03-math-1977$ and $c03-math-1978$ ] if and only if $c03-math-1979$ .
Prove that $c03-math-1980$ and $c03-math-1981$ imply $c03-math-1982$ .
Let $c03-math-1983$ denote the class NP^A and, for k ≥ 1, let $c03-math-1987$ denote the class $c03-math-1988$ . Prove that, for k ≥ 1, if A is $c03-math-1991$ -complete for the class $c03-math-1992$ , then $c03-math-1993$ .

3.2 Prove that there exist sets A,B, such that A≤^SNP_TB but not A≤^P_TB.

3.3 In this exercise, we study the complexity class DP. A language A is in the class DP (D stands for difference) if there exist sets $c03-math-1998$ and $c03-math-1999$ such that $c03-math-2000$ .

The problem SAT-UNSAT asks for two given Boolean formulas ϕ and ψ, whether it is true that ϕ is satisfiable and ψ is unsatisfiable. Prove that SAT-UNSAT is DP-complete under $c03-math-2005$ -reducibility.
Recall the problem EXACT-CLIQUE defined in Example 2.20(b). Show that EXACT-CLIQUE is DP-complete.
The problem CRITICAL HC asks for a given graph $c03-math-2006$ whether it is true that G does not have a Hamiltonian circuit but every graph G^′ obtained from G by adding a new edge has a Hamiltonian circuit. Prove that CRITICAL HC is DP-complete.

3.4 In this exercise, we extend the class DP to the Boolean hierarchy of sets between P and $c03-math-2011$ . For each n ≥ 0, define DP_n as follows: $c03-math-2015$ , $c03-math-2016$ if n is even, and $c03-math-2018$ if n is odd. Then, define $c03-math-2021$ .

In Exercise 2.14, we defined the polynomial-time truth-table reducibility $c03-math-2022$ . We say set A is polynomial-time bounded truth-table reducible to set B, written $c03-math-2025$ , if $c03-math-2026$ via a reduction function f and a set $c03-math-2028$ such that, for any x, $c03-math-2030$ for some constant m ≥ 1. Show that a set A is in BH if and only if A is the union of a finite number of sets in DP if and only if $c03-math-2034$ for some $c03-math-2035$ .
The classes DP_n have complete sets. Define GCOLOR_k be the following problem: Given a graph G, determine whether the chromatic number $c03-math-2040$ of graph G (the minimum number of colors necessary to color graph G) is odd and is between 3k and 4k. Prove that for each odd k, GCOLOR_k is DP_k-complete.
Show that the Boolean hierarchy BH is properly infinite (i.e., $c03-math-2048$ for each n ≥ 0) unless the polynomial-time hierarchy collapses.

3.5 An integer expression E is defined like a regular expression. It contains integer constants and the $c03-math-2051$ and $c03-math-2052$ operations. Each integer expression E represents a set L(E) of integers: $c03-math-2055$ , $c03-math-2056$ , and $c03-math-2057$ .

3.6 The problem INTEGER EXPRESSION EQUIVALENCE (IEE) asks, for two given integer expressions $c03-math-2058$ , whether $c03-math-2059$ . Prove that IEE is $c03-math-2060$ -complete. The problem GRAPH CONSISTENCY (GC) asks, for two given sets A and B of graphs, whether there exists a graph G such that each graph $c03-math-2064$ is isomorphic to a subgraph of G and each graph $c03-math-2066$ is not isomorphic to any subgraph of G. Prove that the problem GC is $c03-math-2068$ -complete.

3.7 In the following, each problem is formulated to be a minimax function f. Prove that the corresponding decision problem of determining whether $c03-math-2070$ for some given graph G and constant K is $c03-math-2073$ -complete. In the following, we write F_n,m to mean the set of all functions $c03-math-2075$ .

MINIMAX-CLIQUE: For a given graph $c03-math-2076$ with its vertices V partitioned into subsets V_i,j, for $c03-math-2079$ , $c03-math-2080$ , find $c03-math-2081$ is a clique in $c03-math-2082$ , where G_t is the induced subgraph of G on the vertex set $c03-math-2085$ .
MINIMAX-CIRCUIT: Given a graph G with its vertex set V partitioned into subsets V_i,j, for $c03-math-2089$ , $c03-math-2090$ , find $c03-math-2091$ has a circuit on $c03-math-2092$ , where G_t is defined as in (a) above.
MINIMAX-3DM: Given mutually disjoint finite sets W_i,j, $c03-math-2095$ , $c03-math-2096$ , and a set S of three-element subsets of $c03-math-2098$ , find $c03-math-2099$ is a matching in $c03-math-2100$ , where W(t) means the set $c03-math-2102$ .
LONGEST DIRECT CIRCUIT: Given a digraph $c03-math-2103$ and a subset E^′ of E, find $c03-math-2106$ has a circuit on $c03-math-2107$ , where G_D is the subgraph of G with vertex set V and edge set $c03-math-2111$ .

3.8 Let CFL denote the class of context-free languages, and let LOGCFL be the class of sets that are reducible to the class CFL under the logarithmic-space reductions.

Prove that $c03-math-2112$ .
Prove that $c03-math-2113$ .

3.9 The transitive closure of a relation R is the set $c03-math-2115$ there exists a sequence of strings $c03-math-2116$ , such that $c03-math-2117$ for all i, $c03-math-2119$ .

Prove that for any relation $c03-math-2120$ with the property $c03-math-2121$ , $c03-math-2122$ .
Prove that there exists a relation $c03-math-2123$ with the property $c03-math-2124$ , such that R^∗ is PSPACE-complete.

3.10 The problem DETERMINISTIC FINITE AUTOMATA INTERSECTION (DFA-INT) asks, for a given sequence of deterministic finite automata $c03-math-2126$ over a common alphabet Σ, whether there exists a string $c03-math-2128$ that is accepted by each M_i, $c03-math-2130$ . Prove that the problem DFA-INT is PSPACE-complete.

3.11 The problem MINIMAL NONDETERMINISTIC FINITE AUTOMATON (MIN-NFA) asks, for a given deterministic finite automaton M and an integer n, whether there exists an equivalent nondeterministic finite automaton that has at most n states. Prove that the problem MIN-NFA is PSPACE-complete.

3.12 Define formally the set G_QBF of game configurations and the relations R₀ and R₁ for the game QBF.

3.13 Prove that it is a polynomially bounded game. Prove that the game GEOGRAPHY played on undirected graphs is solvable in polynomial time.

3.14 The game HEX played between two players 0 and 1 can be defined as follows: The game is played on a graph $c03-math-2137$ with four explicitly marked nodes s₀, t₀, s₁, and t₁. The goal of the game for player 0 is to find a path from s₀ to t₀ and for player 1 is to find a path from s₁ to t₁ by player 1. At the beginning, all but the four special nodes are uncolored, and the four special nodes are colored by $c03-math-2146$ and $c03-math-2147$ . A legal move of player 0 (or player 1) is to mark any uncolored node with the color 0 (or color 1, respectively). The game ends when there is a path from s₀ to t₀ all colored with 0 (and player 0 wins) or when there is a path from s₁ to t₁ all colored with 1 (and player 1 wins).

Define formally the set $c03-math-2152$ of game configurations and the relations R₀ and R₁. Prove that HEX is a polynomially bounded game.
Prove that game HEX is PSPACE-complete.

3.15 Give a proof for Corollary 3.20 without using the notion of ATMs (instead, using the idea of the proof of Theorem 3.18 directly).

3.16 Verify that the size of the machine M_C of Theorem 3.31 is bounded by $c03-math-2156$ for some polynomial p.

3.17 Consider the following variation of the game BFG:

The variables of the formula F are partitioned into two subsets, X and Y.
In one move, player 0 (player 1) can change the value of at most one variable in X (respectively, in Y).
The initial assignment τ₀ makes F false.
A player wins if the formula becomes true after his/her move.

Prove that this version of the game BFG is also EXP-complete.

3.18 Prove Theorem 3.33.

3.19 Prove Theorem 3.34.

3.20 The problem ORACLE-SAT is defined as follows: Let G be a Boolean formula over five sets of variables $c03-math-2166$ , Y, and Z, where $c03-math-2169$ for $c03-math-2170$ , and $c03-math-2171$ . Determine whether it is true that there exists a Boolean function $c03-math-2172$ such that for all assignments $c03-math-2173$ , G is satisfied by π and τ, where $c03-math-2177$ is defined by $c03-math-2178$ . (If $c03-math-2179$ , then we write $c03-math-2180$ to denote the string of n bits: $c03-math-2182$ .) Prove that ORACLE-SAT is $c03-math-2183$ -complete for NEXP.

Historical Notes

The polynomial-time hierarchy was first introduced by Stockmeyer and Meyer (1973) as a polynomial-time analog of the arithmetic Hierarchy (Rogers, 1967). Stockmeyer (1977) and Wrathall (1977) contain complete sets SAT_k and the alternating quantifier characterizations. Stockmeyer (1977) also contains the $c03-math-2185$ -complete problem IEE (Exercise 3.5). The $c03-math-2186$ -complete problem GRN is from Ko and Lin (1995a). ATMs are first defined in Chandra et al. (1981). The simulations between ATMs, DTMs, and NTMs are proven there. The alternating quantifier characterization of PSPACE and the PSPACE-complete problems QBF are from Stockmeyer and Meyer (1973), and the PSPACE-completeness of TRE is from Meyer and Stockmeyer (1972). The first natural PSPACE-complete two-person game is HEX (Exercise 3.14), proved in Even and Tarjan (1976). Schaefer (1978b) contains many other PSPACE-complete games, including the game GEOGRAPHY. The idea of using TMs to encode objects of exponential size has been used in many applications; see, for instance, Ko (1992) for the EXP-complete problem EXP-CVP. The game BFG (Theorem 3.32 and Exercise 3.17) is from Stockmeyer and Chandra (1979). The EXPSPACE-complete problem TERE is from Hunt (1973).

The notion of strong-NP reducibility was introduced by Long (1982). A related strong-NP many-one reducibility was first used by Adleman and Manders (1977). The class DP and the corresponding DP-complete problems were studied in Papadimitriou and Yannakakis (1984) and Papadimitriou and Wolfe (1987). The Boolean hierarchy has been studied by a number of people. A comprehensive study was presented in Cai et al. (1988, 1989). The $c03-math-2187$ -complete problem GC (Exercise 3.6) is from Ko and Tzeng (1991). The $c03-math-2188$ -complete problems in Exercise 3.7 are from Ko and Lin (1995a). The class LOGCFL has been studied in connection with parallel complexity. Exercise 3.8(a) is from Ruzzo (1980) and Exercise 3.8(b) is from Sudborough (1978). The complexity of transitive closure was studied in Book and Wrathall (1982) and Ko (1985a). The DFA Intersection problem is from Kozen (1977) and the minimal NFA problem is from Jiang and Ravikumar (1993).

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.6

Create new playlist

Sign In

Sign Up

Theorem 3.28

Proof

Theorem 3.29

Proof

3.6 EXP-Complete Problems

Proposition 3.30

Proof

Theorem 3.31

Proof

Theorem 3.32

Proof

Theorem 3.33

Theorem 3.34

Exercises

Historical Notes

Table of Contents for
3.6