ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: Feigenbaum, Joan, AT&T Labs – Research, Florham Park, NJ 07932-0971 USA Games, Complexity Classes, and Approximation Algorithms

Game theory provides a framework in which to model and analyze conflict and cooperation among independent decision makers. Many areas of computer science have benefitted from this framework, including artificial intelligence, distributed computing, security and privacy, and lower bounds. Games are particularly important in computational complexity, where they are used to characterize complexity classes, to understand the power and limitations of those classes, and to interpret the complete problems for those classes. A standard example of the use of games to characterize complexity classes is the well-known result of Chandra, Kozen, and Stockmeyer [CKS] that Alternating Polynomial Time (APTIME) is identical to Polynomial Space (PSPACE). An alternating, polynomial-time machine and an input x of length n determine a zero-sum, perfect-information game for which the game tree has depth polynomial in n. The referee R is a deterministic, polynomialtime machine that reads an entire played game before deciding whether the winner is Player P_{1} (who claims that x is in the APTIME set L) or Player P_{2} (who claims that x is not in L). P_{1} (resp. P_{2}) has a winning strategy if and only if x is in L (resp. x is not in L). Because P_{1}, P_{2}, and R are deterministic, R always decides the winner correctly; in game-theoretic terms, the value of the game is 1 if x is in L, and it is 0 if x is not in L. Subsequent results of Papadimitriou [P], Babai and Moran [BM], Lund, Fortnow, Karloff and Nisan [LFKN], and Shamir [S] show that the connection between PSPACE and zero-sum, perfect-information, polynomialdepth games is quite robust. Both [P] and [BM] modify the basic computational model of APTIME so that Player P_{2} uses a trivial strategy: Whenever it is his turn to move, i. e., to write down a p(n)-bit string for some polynomial p, P_{2} simply writes down the results of p(n) fair coin-flips. Now if P_{1} plays optimally on input string x, there is some probability (computed over the coin tosses of P_{2}) that R declares P_{1} to be the winner; that probability is the value of the game determined by x, P_{1}, and R. In Papadimitriou’s “games against nature, ” x is in L if and only if the value of the game is at least 1/2. In Babai and Moran’s “Arthur-Merlin games, ” x is in L if the value of the game is at least 2/3, and x is not in L if the value is at most 1/3. Under both definitions, the class of sets accepted by such a game system is still PSPACE. (This was proven in [P] for games against nature and in [LFKN] and [S] for Arthur-Merlin games.) Thus we get the same computational complexity class from zero-sum, perfect-information, polynomial-depth games whether P_{2} is a strategic player or a random player and whether we demand that the referee compute the value of the game exactly (as in games against nature) or approximately (as in Arthur-Merlin games). In this talk, I will present two recent characterizations of PSPACE that push its identification with zero-sum, perfect-information, polynomial-depth games even further. The Probabilistically Checkable Debate System model (PCDS) is obtained by modifying the APTIME model in two ways: The polynomial-time referee R is allowed to flip coins, and it is not necessarily allowed to read the entire transcript of a played game before deciding whether the winner is P_{1} or P_{2}. If x is in L, then R must decide in P_{1}’s favor with probability 1, and if x is not in L, then R must decide in P_{2}’s favor with probability at least 2/3. In the Randomized PCDS model (RPCDS), Player P_{1} and referee R are exactly as in PCDS, but Player P_{2} must play by flipping a sequence of fair coins. Condon, Feigenbaum, Lund, and Shor [CFLS1, CFLS2] show that a set is in PSPACE if and only if it is recognized by a PCDS and by an RPCDS each of which allows its referee to flip O(log n) coins and to read only a constant number of bits of the game transcript. If time allows, I will present two related set of results about games and complexity. The first uses these characterizations to show that certain natural maximization and minimization functions, drawn from domains such as propositional logic, graph searching, graph reliability, and stochastic optimization, are as hard to approximate closely as they are to compute exactly. The second is a general framework defined by Feigenbaum, Koller, and Shor [FKS] and further developed by Feige and Kilian [FK] in order to explore relationships between complexity classes and imperfect-information games. Some tight characterizations of exponential-time complexity classes are obtained, but no class of imperfect-information games can be as robustly identified with any complexity class as perfect-information, polynomial-depth games can be with PSPACE. References:

[BM] L. Babai and S. Moran, “Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes, ” Journal of Computer and System Sciences, 36 (1988), pp. 254-276.

[CKS] A. Chandra, D. Kozen, and L. Stockmeyer, “Alternation, ” Journal of the Association for Computing Machinery, 28 (1981), pp. 114-133.

[CFLS1] A. Condon, J. Feigenbaum, C. Lund, and P. Shor, “Probabilistically Checkable Debate Systems and Nonapproximability Results for PSPACE-Hard Functions, ” Chicago Journal of Theoretical Computer Science, volume 1995, number 4.

http://www.cs.uchicago.edu/publications/cjtcs/articles/1995/4/contents.html.

[CFLS2] A. Condon, J. Feigenbaum, C. Lund, and P. Shor, “Random Debaters and the Hardness of Approximating Stochastic Functions, ” SIAM Journal on Computing, 26 (1997), pp. 369-400.

[FK] U. Feige and J. Kilian, “Making Games Short, ” in Proceedings of the 29th Symposium on Theory of Computing, ACM Press, New York, 1997, pp. 506-516.

[FKS] J. Feigenbaum, D. Koller, and P. Shor, “A Game-Theoretic Classification of Interactive Complexity Classes, ” in Proceedings of the 10th Conference on Structure in Complexity Theory, IEEE Computer Society Press, Los Alamitos, 1995, pp. 227-237.

[LFKN] C. Lund, L. Fortnow, H. Karloff, and N. Nisan, “Algebraic Methods for Interactive Proof Systems, ” Journal of the Association for Computing Machinery, 39 (1992), pp. 859-868.

[P] C. Papadimitriou, “Games Against Nature, ” Journal of Computer and System Sciences, 31 (1985), pp. 288-301.

[S] A. Shamir, “IP = PSPACE, ” Journal of the Association for Computing Machinery, 39 (1992), pp. 869-877.