% The Chicago Journal of Theoretical Computer Science, Volume 1995, Article 4 % Published by MIT Press, Cambridge, Massachusetts USA % Copyright 1995 by Massachusetts Institute of Technology % \newtoks\rstyle \rstyle={cjlook} % \ifx\documentclass\undeftex \documentstyle[v1.1,published]{cjstruct} \else \documentclass[v1.1,published]{cjstruct} \fi % % Local macro definitions for this article. % \catcode`\@=11 \ifx\nopagebreakbeginpar\undeftex \newcommand{\nopagebreakbeginpar}{\@beginparpenalty10000} \fi \ifx\nopagebreakendpar\undeftex \newcommand{\nopagebreakendpar}{\@endparpenalty10000} \fi \catcode`\@=12 % \ifx\placeepsinpic\undeftex \newcommand{\placeepsinpic}[3]{% \epsfxsize=#1% \epsfxsize=\epscompmagnification{#1}{#2}{#3}\epsfxsize% \epsfbox{#3.eps}% } \fi % \ifltwoe\else\newcommand{\emph}[1]{{\em #1\/}}\fi \ifltwoe\else\newcommand{\textit}[1]{{\it #1\/}}\fi \ifltwoe\else\newcommand{\upshape}{\fontshape{n}\selectfont}\fi % \newcommand{\prooffontshape}{\upshape} \newcommand{\exampfontshape}{\upshape} % \newcommand{\textuprm}[1]{\textup{\textrm{#1}}} % \mathstyleclass{\complexityclass}{\mathord}{\textsl} \mathstyleclass{\systemmodel}{\mathord}{\textuprm} \mathstyleclass{\inputset}{\mathord}{\textuprm} \mathstyleclass{\problemset}{\mathord}{\textuprm} \mathstyleclass{\problemfunc}{\mathord}{\textuprm} % \newcommand{\complement}[1]{\mathord{\mbox{\sl co\begin{math}#1\end{math}}}} % \newcommand{\orderge}[1]{\Omega(#1)} \newcommand{\orderlt}[1]{o(#1)} \newcommand{\orderle}[1]{O(#1)} % \newcommand{\intdiv}{\mathbin{\mbox{\textup{\textrm{div}}}}} \newcommand{\hamming}{\mathord{\mbox{\textup{\textrm{Ham}}}}} \newcommand{\polyof}{\mathord{\mbox{\textup{\textrm{poly}}}}} % \newcommand{\strlnth}[1]{\mathopen{|}#1\mathclose{|}} \newcommand{\setof}[2]{\{\,#1\mid#2\,\}} \newcommand{\bigsetof}[2]{\left\{\left.#1\right|#2\right\}} \newcommand{\setunion}{\cup} \newcommand{\setsize}[1]{\mathopen{|}#1\mathclose{|}} \newcommand{\oftype}{\mathpunct{:}} \newcommand{\funcspace}[2]{#1\mathbin{\rightarrow}#2} \newcommand{\logicor}{\vee} \newcommand{\logicand}{\wedge} \newcommand{\logicimplies}{\Rightarrow} % % end of local macro definitions for this article % \begin{document} % \begin{articleinfo} % \publisher{The MIT Press} % \publishercomment{% {\Large \begin{center} Volume 1995, Article 4\\ \textit{19 October 1995} \end{center} } \par\noindent ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA 02142 USA; (617)253-2889; \emph{journals-orders@mit.edu, journals-info@mit.edu}\@. Published one article at a time in \LaTeX\ source form on the Internet\@. Pagination varies from copy to copy\@. For more information and other articles see: \begin{itemize} \item \emph{http://www-mitpress.mit.edu/jrnls-catalog/chicago.html} \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/} \item \emph{gopher.mit.edu} \item \emph{gopher.cs.uchicago.edu} \item anonymous \emph{ftp} at \emph{mitpress.mit.edu} \item anonymous \emph{ftp} at \emph{cs.uchicago.edu} \end{itemize} \sentence } % \copyrightstmt{% \copyright 1995 The Massachusetts Institute of Technology\@. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to insure fair attribution to authors and the journal, and to prohibit use in a competing commercial product\@. See the journal's World Wide Web site for further details\@. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; \emph{journals-rights@mit.edu}\@.\pagebreak[2] } % \journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science} % \journalcomment{% The \emph{Chicago Journal of Theoretical Computer Science} is a peer-reviewed scholarly journal in theoretical computer science\@. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science\@. \par \begin{trivlist} \item[\emph{Editor in chief:}] Janos Simon \item[\emph{Consulting editors:}] Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel \item[\emph{Editors:}] \begin{tabular}[t]{lll} Martin Abadi & Greg Frederickson & John Mitchell \\ Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\ Eric Allender & Georg Gottlob & Gil Neiger \\ Tetsuo Asano & Vassos Hadzilacos & David Peleg \\ Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\ Eric Bach & Maurice Herlihy & James Royer \\ Stephen Brookes & Stephen Homer & Alan Selman \\ Jin-Yi Cai & Neil Immerman & Nir Shavit \\ Anne Condon & Paris Kanellakis & Eva Tardos \\ Cynthia Dwork & Howard Karloff & Sam Toueg \\ David Eppstein & Philip Klein & Moshe Vardi \\ Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\ Lance Fortnow & Stephen Mahaney & Pierre Wolper \\ Steven Fortune & Michael Merritt \end{tabular} \vspace{1ex} \item[\emph{Managing editor:}] Michael J.\ O'Donnell \vspace{1ex} \item[\emph{Electronic mail:}] \emph{chicago-journal@cs.uchicago.edu} \end{trivlist} \sentence } % \bannerfile{cjtcs-banner.tex} % \volume{1995} % \articleid{4} % \selfcitation{ @article{cj95-04, author={Anne Condon and Joan Feigenbaum and Carsten Lund and Peter W. Shor}, title={Probabilistically Checkable Debate systems and Nonapproximability of \(\textsl{PSPACE}\)-Hard Functions} journal={Chicago Journal of Theoretical Computer Science}, volume={1995}, number={4}, publisher={MIT Press}, month={September}, year={1995} } } % \begin{retrievalinfo} \end{retrievalinfo} % \title{Probabilistically Checkable Debate Systems and Nonapproximability of \protect\(\complexityclass{PSPACE}\protect\)-Hard\nolinebreak[1] Functions} \shorttitle{Probabilistic Debate Systems} \collectiontitle{} \begin{authorinfo} % % Correction to error in cjstruct.sty version 1.1. % \def\fixversion{1.1} \ifx\cjversion\fixversion \renewcommand{\printname}[1]{ \global\authorstring={#1} \global\authorstrue \ifinfo\item Printed name: #1\fi } \fi % % End of correction. % \printname{Anne Condon} \collname{}{Condon, Anne} \begin{institutioninfo} \instname{University of Wisconsin} \department{Computer Sciences Department} \address{1210 West Dayton Street}{Madison}{WI}{USA}{57306} \end{institutioninfo} \email{condon@cs.wisc.edu} \end{authorinfo} % \begin{authorinfo} \printname{Joan Feigenbaum} \collname{}{Feigenbaum, Joan} \begin{institutioninfo} \instname{AT\&T Bell Laboratories} \address{600 Mountain Avenue, P.O. Box 636}{Murray Hill}{NJ}{USA}{07974-0636} \end{institutioninfo} \email{jf@research.att.com} \end{authorinfo} % \begin{authorinfo} \printname{Carsten Lund} \collname{}{Lund, Carsten} \begin{institutioninfo} \instname{AT\&T Bell Laboratories} \address{600 Mountain Avenue, P.O. Box 636}{Murray Hill}{NJ}{USA}{07974-0636} \end{institutioninfo} \email{lund@research.att.com} \end{authorinfo} % \begin{authorinfo} \printname{Peter W. Shor} \collname{}{Shor, Peter W.} \begin{institutioninfo} \instname{AT\&T Bell Laboratories} \address{600 Mountain Avenue, P.O. Box 636}{Murray Hill}{NJ}{USA}{07974-0636} \end{institutioninfo} \email{shor@research.att.com} \end{authorinfo} % \shortauthors{Condon, Feigenbaum, Lund, Shor} % \support{% Anne Condon's work was supported in part by NSF grants CCR-9100886 and CCR-9257241\@.% } % \begin{editinfo} \submitted{12}{6}{1994}\reported{5}{4}{1995} \submitted{22}{5}{1995}\reported{25}{5}{1995} \submitted{9}{6}{1995}\reported{12}{6}{1995}\published{19}{10}{1995} \end{editinfo} \end{articleinfo} % \begin{articletext} % \begin{abstract} % \apar{Abstract-1} We initiate an investigation of \emph{probabilistically checkable debate systems} (\(\systemmodel{PCDS}\)), a natural generalization of probabilistically checkable proof systems (\(\systemmodel{PCPS}\))\@. A \(\systemmodel{PCDS}\) for a language \(L\) consists of a probabilistic polynomial-time verifier \(V\) and a debate between player \(1\), who claims that the input \(x\) is in \(L\), and player \(0\), who claims that the input \(x\) is not in \(L\)\@. We show that there is a \(\systemmodel{PCDS}\) for \(L\) in which \(V\) flips \(\orderle{\log n}\) random coins and reads \(\orderle{1}\) bits of the debate if and only if \(L\) is in \(\complexityclass{PSPACE}\)\@. This characterization of \(\complexityclass{PSPACE}\) is used to show that certain \(\complexityclass{PSPACE}\)-hard functions are as hard to approximate closely as they are to compute exactly\@. \end{abstract} % These results first appeared in our Technical Memorandum~\cite{cj95-04-7}\@. They were presented in preliminary form at the 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, May 1993, titled ``Probabilistically Checkable Debate Systems and Approximation Algorithms for \(\complexityclass{PSPACE}\)-Hard Functions''~\cite{cj95-04-8}\@. % \asection{1}{Introduction} % \apar{1-1} Suppose that two candidates, \(B\) and \(C\), agree to a debate format\@. Voter \(V\) is too busy to catch more than a very small number of bits of the debate\@. How does \(V\) decide whether \(B\) or \(C\) won the debate\@? In this paper, we show that if \(B\) and \(C\) choose the right debate format, \(V\)'s problem is solved\@. By listening to a few randomly chosen sound bites of the debate, \(V\) can with near certainty figure out who won\@. % \apar{1-2} Similarly, suppose that \(B\) or \(C\) is giving a speech to a set of voters \(V_1,\ldots,V_n\), represented by finite automata\@. He would like to give the speech that results in acceptance (votes) by the greatest number of voters \(V_i\)\@. We show that not only can he not compute this maximum exactly, but he cannot come within an arbitrary constant factor, unless he has access to an oracle (political consultant) with the full power of \(\complexityclass{PSPACE}\)\@. % \apar{1-3} Our work builds on recent progress in the theory of \emph{probabilistically checkable proof systems} (\(\systemmodel{PCPS}\))\@. Results about the language-recognition power of \(\systemmodel{PCPS}\)s have led to lower bounds on the difficulty of approximating \(\complexityclass{NP}\)-hard functions\@. In this paper, we define \emph{probabilistically checkable debate systems} (\(\systemmodel{PCDS}\)s)\@. We prove several results about the language-recognition power of \(\systemmodel{PCDS}\)s and then use them to obtain lower bounds on the difficulty of approximating \(\complexityclass{PSPACE}\)-hard functions\@. % \apar{1-4} Let us describe the background for this work in more detail\@. Loosely speaking, a language \(L\) has a \(\systemmodel{PCPS}\) if, for every \(x\in L\), there is a string \(\pi\) such that a probabilistic verifier \(V\) taking \(x\) and \(\pi\) as input can be convinced with high probability that \(x\in L\)\@. The class \(\complexityclass{PCP}(r(n),q(n))\) consists of those languages recognizable by \(\systemmodel{PCPS}\)s in which the verifier uses \(\orderle{r(n)}\) coin flips and looks at \(\orderle{q(n)}\) bits\@. It is known that \(\complexityclass{PCP}(\log n,1)=\complexityclass{NP}\) (cf.~\cite{cj95-04-1} and~\cite{cj95-04-2})\@. % \apar{1-5} Results on the power of classes \(\complexityclass{PCP}(r(n),q(n))\) can be used to show that many approximation problems are hard, unless there is some unexpected collapse of complexity classes\@. The first result along these lines was proven by Condon~\cite{cj95-04-6}\@. Additional results concern the \(\problemfunc{MAX-CLIQUE}\) problem~\cite{cj95-04-11}---given an undirected graph, find a maximal-size set of nodes with an edge between every pair in the set\@. In a seminal paper, Feige et al.~\cite{cj95-04-10} showed that \(\problemfunc{MAX-CLIQUE}\) is difficult to approximate\@. The result of \cite{cj95-04-10} has been improved several times, and it is now known that there is an \(\epsilon\) such that approximating \(\problemfunc{MAX-CLIQUE}\) within a factor of \(n^\epsilon\) is as difficult as solving \(\complexityclass{NP}\)-complete problems exactly~\cite{cj95-04-1}\@. Furthermore, there is a large class of natural optimization problems, those hard for the class \(\complexityclass{MAX-SNP}\) defined in~\cite{cj95-04-20}, that do not have polynomial-time approximation schemes unless \(\complexityclass{P}=\complexityclass{NP}\); that is, for each of these problems, there is an \(\epsilon\) such that approximating the optimal solution within ratio \(\epsilon\) is as hard as solving \(\complexityclass{NP}\)-complete problems exactly~\cite{cj95-04-1}\@. This result on \(\complexityclass{MAX-SNP}\) shows that many well-known optimization problems are hard to approximate closely, including Traveling Salesman with Triangle Inequality, \(\problemfunc{MAX-SAT}\), and \(\problemfunc{MAX-CUT}\)\@. % \apar{1-6} A \(\systemmodel{PCDS}\) is a generalization of a \(\systemmodel{PCPS}\)\@. In a \(\systemmodel{PCDS}\) for \(L\), there are two computationally powerful players, \(1\) and \(0\) (called \(B\) and \(C\) at the beginning of this section) and a probabilistic polynomial-time verifier \(V\)\@. Players \(1\) and \(0\) play a game in which they alternately write out strings on a debate tape \(\pi\)\@. Player \(1\)'s goal is to convince \(V\) that an input \(x\in L\), and player \(0\)'s goal is to convince \(V\) that \(x\notin L\)\@. When the debate is over, \(V\) looks at \(x\) and \(\pi\) and decides whether \(x\in L\) (player \(1\) wins the debate) or \(x\notin L\) (player \(0\) wins the debate)\@. Suppose \(V\) flips \(\orderle{r(n)}\) random coins, and reads \(\orderle{q(n)}\) bits of \(\pi\)\@. If, under the best strategies of players \(1\) and \(0\), \(V\)'s decision is correct with high probability, then we say that \(L\) is in \(\complexityclass{PCD}(r(n),q(n))\)\@. % \apar{1-7} Specifically, we say that a language \(L\) is in \(\complexityclass{PCD}(r(n),q(n))\) if it has a nonadaptive \(\systemmodel{PCDS}\) with one-sided error in which players \(1\) and \(0\) write on a debate tape, and then \(V\) makes \(\orderle{r(n)}\) coin flips and queries \(\orderle{q(n)}\) bits based on these coin flips\@. By ``nonadaptive,'' we mean that the choice of bits queried by \(V\) is based solely on the input and the coin flips\@. By ``one-sided error,'' we mean that whenever \(x\in L\), \(V\) must correctly decide that \(x\in L\), no matter which sequence of \(\orderle{r(n)}\) coins are flipped (assuming correct play on the part of player \(1\))\@. When \(x\notin L\), \(V\) is allowed to conclude incorrectly that \(x\in L\) with probability at most \(\epsilon\), for some fixed \(\epsilon<1\)\@. % \apar{1-8} Note that we defined \(\systemmodel{PCDS}\)s so that the two players must be deterministic, whereas the verifier can use randomization\@. Allowing the players to use randomization would not change the class \(\complexityclass{PCD}(r(n),q(n))\); this follows from the standard game-theoretic result that, in perfect information games, players always have deterministic strategies that are optimal~\cite{cj95-04-3}\@. % \apar{1-9} With the above definition in hand, we can state our main results about the language-recognition power of \(\systemmodel{PCDS}\)s\@. % \begin{alabsubtext}{Theorem}{3}{Section~3} \(\complexityclass{PSPACE}=\complexityclass{PCD}(\log n,1)\)\@. \end{alabsubtext} % This result is the best possible, because one can show that \(\complexityclass{PCD}(\log n,q(n))\) is contained in \(\complexityclass{PSPACE}\), for every function \(q\)\@. % \apar{1-10} The following is a technical building block, interesting in its own right, that is used in the proof that \(\complexityclass{PSPACE}=\complexityclass{PCD}(\log n,1)\): If \(r(n)=\orderge{\log n}\), then \(\complexityclass{PCD}(r(n),q(n))\) contains the same languages if the verifier reads \(\orderle{q(n)}\) \emph{rounds} of the debate as it does if the verifier reads \(\orderle{q(n)}\) \emph{bits} of the debate\@. % \apar{1-11} We use our main result about the language-recognition power of \(\systemmodel{PCDS}\)s to prove lower bounds on the difficulty of approximating \(\complexityclass{PSPACE}\)-hard functions\@. Let \(\problemfunc{\(\problemfunc{MAX-Q3SAT}\)}\) be the following natural optimization version of the canonical \(\complexityclass{PSPACE}\)-complete language \(\problemset{QBF}\) (the set of true quantified Boolean formulae)\@. Suppose \[\Phi=Q_1 x_1 Q_2 x_2\cdots Q_n x_n\phi(x_1,x_2,\ldots,x_n)\] is a quantified Boolean formula, with \(Q_i\in\{\exists,\forall\}\), and \(\phi\) in \(\inputset{3CNF}\)\@. Suppose that the variables of the formula are chosen, in order of quantification, by two players \(0\) and \(1\), where player \(0\) chooses the universally quantified variables and player \(1\) chooses the existentially quantified variables\@. If player \(1\) can guarantee that \(k\) clauses of \(\phi\) will be satisfied by the resulting assignment, regardless of what player \(0\) chooses, we say that \(k\) clauses of \(\Phi\) are \emph{simultaneously satisfiable}\@. We let \(\problemfunc{\(\problemfunc{MAX-Q3SAT}\)}\) be the function that maps a quantified \(\inputset{3CNF}\) formula \(\Phi\) to the maximum number of simultaneously satisfiable clauses\@. % \begin{alabsubtext}{Theorem}{4}{Section~4} % There is a constant \(0<\epsilon<1\) such that approximating \(\problemfunc{MAX-Q3SAT}\) within ratio \(\epsilon\) is \(\complexityclass{PSPACE}\)-hard\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % \end{alabsubtext} % Thus \(\problemfunc{MAX-Q3SAT}\) is as hard to approximate closely as it is to compute exactly\@. % \apar{1-12} We use reductions to prove that certain other \(\complexityclass{PSPACE}\)-hard functions are \(\complexityclass{PSPACE}\)-hard to approximate in a stronger sense\@. These include maximization versions of the Finite Automata Intersection problem, shown \(\complexityclass{PSPACE}\)-complete by Kozen~\cite{cj95-04-16}, and the Generalized Geography problem, shown \(\complexityclass{PSPACE}\)-complete by Schaefer~\cite{cj95-04-21}\@. We show that there is a constant \(\epsilon\) such that approximating these problems within ratio \(n^\epsilon\) is \(\complexityclass{PSPACE}\)-hard\@. % \apar{1-13} The rest of this paper is organized as follows\@. We define \(\systemmodel{PCDS}\)s, and all of our other terms, precisely in Section~2\@. Our results on the language-recognition power of \(\systemmodel{PCDS}\)s are given in Section~3\@. Those on approximation of \(\complexityclass{PSPACE}\)-hard functions are given in Section~4\@. Section~5 contains open questions and a discussion of subsequent related results\@. % \asection{2}{Preliminaries} % \apar{2-1} We first review the definition of a \(\systemmodel{PCPS}\) (probabilistically checkable proof system)\@. A \emph{verifier} is a probabilistic polynomial-time Turing machine that takes as input a pair \(x,\pi\), where \(\pi\in\{0,1\}^*\), and either accepts or rejects\@. A language \(L\) has a probabilistically checkable proof system, or \(\systemmodel{PCPS}\), with error probability \(\epsilon\) if there is a verifier \(V\) with the following properties: % \begin{itemize} \item for all \(x\) in \(L\), there is a string \(\pi\) such that \(V\) accepts with probability \(1\) on input \(x, \pi\); and \item for all \(x\) not in \(L\), on all strings \(\pi\), \(V\) accepts with probability at most \(\epsilon\) on input \(x,\pi\)\@. \end{itemize} % \apar{2-2} We say that the verifier makes \(q(n)\) queries if the number of bits of \(\pi\) read by the verifier is at most \(q(n)\), when the input is of size \(n\)\@. \(\complexityclass{PCP}(r(n)\),\(q(n)\)) is the class of languages that have probabilistically checkable proof systems with error probability \(\frac{1}{2}\) in which the verifier uses \(\orderle{r(n)}\) random bits and makes \(\orderle{q(n)}\) queries\@. % \apar{2-3} We next extend this to define \(\systemmodel{PCDS}\)s\@. A probabilistically checkable debate system, or \(\systemmodel{PCDS}\), consists of a verifier \(V\) and a {\em debate format} \(D\)\@. As before, the verifier is a probablistic polynomial-time Turing machine that takes as input a pair \(x,\pi\), where \(\pi\in\{0,1\}^*\), and outputs \(1\) or \(0\)\@. We interpret these outputs to mean ``player \(1\) won the debate'' and ``player \(0\) won the debate,'' respectively\@. % \apar{2-4} A debate format is a pair of functions \(f(n),g(n)\)\@. Informally, for a fixed \(n\), a debate between two players, \(0\) and \(1\), consistent with format \(f(n),g(n)\), contains \(g(n)\) rounds\@. At round \(i\ge 1\), player \(i\bmod 2\) chooses a string of length \(f(n)\)\@. % \apar{2-5} For each \(n\), corresponding to the debate format \(D\) is a \emph{debate tree}\@. This is a complete binary tree of depth \(f(n)g(n)\) such that, from each node, one edge is labeled \(0\) and the other is labeled \(1\)\@. A \emph{debate} is any string of length \(f(n)g(n)\)\@. Thus, there is a one-to-one correspondence between debates and the paths in the debate tree\@. Moreover, a debate is the concatenation of \(g(n)\) substrings of length \(f(n)\)\@. Each substring is called a \emph{round} of the debate, and each debate of this debate tree has \(g(n)\) rounds\@. % \apar{2-6} Again for a fixed \(n\), a \emph{debate subtree} is a subtree of the debate tree of depth \(f(n) g(n)\) such that each node at level \(i\) (the root is at level \(0\)) has one child if \(i\intdiv f(n)\) is even, and it has two children if \(i\intdiv f(n)\) is odd\@. Informally, a debate subtree corresponds to a list of ``responses'' of player \(1\), against \emph{all possible} ``arguments'' of player \(0\) in the debate\@. For this reason, we also refer to a debate subtree as a \emph{strategy} of player 1\@. A strategy of player \(0\) can be defined in a similar way (where the definition of debate subtree is modified so that each node at level \(i\) has one child if \(i\intdiv f(n)\) is odd, and two children if \(i\intdiv f(n)\) is even)\@. Thus, a pair of strategies, one for each player, defines a unique debate---namely, the unique path in the intersection of the strategies (represented as trees) of the players\@. % \apar{2-7} A strategy of player \(1\) could also be defined as a function from nodes of the complete binary tree on levels \(i\) where \(i\intdiv f(n)\) is even into \(\{0,1\}\), i.e., into responses of player \(1\)\@. The debate subtree corresponding to such a function is simply the subtree of the complete binary tree that is reachable from the root via paths of the following form: At nodes on level \(i\) where \(i\intdiv f(n)\) is even, follow the outgoing edge selected by the strategy function; at nodes on level \(j\) where \(j\intdiv f(n)\) is odd, follow either outgoing edge\@. However, representing a strategy as a function requires determining responses for many nodes of the game tree that can never be reached with that strategy\@. Furthermore, the proof of our main result is more naturally expressed in terms of subtrees than functions\@. For these reasons, we define strategies as subtrees\@. % \apar{2-8} A language \(L\) has a \(\systemmodel{PCDS}\) \emph{with error probability} \(\epsilon\) if there is a pair \((D,V)\) where \(D=(f(n),g(n))\), with the following properties: % \begin{itemize} \item For all \(x\) in \(L\), there is a debate subtree such that, for all debates \(\pi\) labeling a path of this subtree, \(V\) outputs 1 with probability \(1\) on input \(x,\pi\)\@. In this case, we say that \(x\) is accepted by \((D,V)\)\@. \item For all \(x\) not in \(L\), on all debate subtrees, there exists a debate \(\pi\) labeling some path of the subtree such that \(V\) outputs \(1\) with probability at most \(\epsilon\) on input \(x,\pi\)\@. In this case, we say that \(x\) is rejected by \((D,V)\)\@. \end{itemize} % Equivalently, the first condition states that on all \(x\) in \(L\), player \(1\) has a strategy such that, for every strategy of player \(0\), \(V\) outputs \(1\) with probability \(1\) on the debate defined by the pair of strategies\@. The second condition states that on all \(x\) not in \(L\), player \(0\) has a strategy such that, for every strategy of player \(1\), \(V\) outputs \(1\) with probability at most \(\epsilon\) on the debate defined by the pair of strategies\@. % \apar{2-9} This definition allows ``one-sided error,'' analogous to the type of errors that are allowed in the complexity class \(\complement{\complexityclass{RP}}\)\@. We could also define a class of \(\systemmodel{PCDS}\)s with ``zero-sided error,'' with three possible outputs, \(1\), \(0\), and \(\Lambda\), for ``player \(1\) won,'' ``player \(0\) won,'' and ``I don't know who won,'' respectively\@. In this case, the verifier must never declare the losing player to be a winner, but it may, both in the case that \(x\in L\) and in the case that \(x\notin L\), say that it doesn't know who won\@. We will see in Corollary~2 that this definition also gives the class \(\complexityclass{PSPACE}\)\@. % \apar{2-10} As in the theory of \(\systemmodel{PCPS}\)s, we say that the verifier makes \(q(n)\) queries if the number of bits of \(\pi\) read by the verifier is at most \(q(n)\) when the input is of size \(n\)\@. The verifier \(V\) in a \(\systemmodel{PCDS}\) is required to be nonadaptive (the bits of \(\pi\) read by \(V\) depend solely on the input and the coin flips)\@. If \(L\) has a \(\systemmodel{PCDS}\) with error probability \(\frac{1}{2}\) in which \(V\) flips \(\orderle{r(n)}\) coins and reads \(\orderle{q(n)}\) bits of \(\pi\), we say that \(L\in\complexityclass{PCD}(r(n),q(n))\)\@. % \apar{2-11} It will be convenient in later proofs to reason about a generalized class, \(\complexityclass{GPCD}(r(n), q(n))\)\@. This class is defined exactly as \(\complexityclass{PCD}(r(n),q(n))\), except that the verifier of a \(\systemmodel{GPCDS}\) (Generalized Probabilistic Debate System) nonadaptively queries \(\orderle{q(n)}\) \emph{rounds} of the debate \(\pi\) (rather than \(\orderle{q(n)}\) \emph{bits} of the debate)\@. Thus, in a \(\systemmodel{GPCDS}\), there is no restriction on the number of bits queried by the verifier in each round\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % \apar{2-12} Next, we give some definitions relating to approximability of \(\complexityclass{PSPACE}\)-hard functions\@. Let \(f\) be any real-valued function with domain \(D\subseteq\{0,1\}^*\)\@. Let \(A\) be an algorithm that, on input \(x\in\{0,1\}^*\), produces an output \(A(x)\)\@. We say that \(A\) \emph{approximates \(f\) within ratio} \(\epsilon(n)\), \(0<\epsilon(n)<1\), if for all \(x\in D\), \(\epsilon(\strlnth{x})\le A(x)/f(x)\le 1/\epsilon(\strlnth{x})\)\@. If \(\epsilon(n)>1\), then ``\(A\) approximates \(f\) within ratio \(\epsilon(n)\)'' means that \(1/\epsilon(\strlnth{x})\le A(x)/f(x)\le\epsilon(\strlnth{x})\)\@. If algorithm \(A\) computes the function \(g\), we also say that \(g\) approximates \(f\) within ratio \(\epsilon\)\@. % \apar{2-13} The function \(f\) has a \emph{polynomial-time approximation scheme}, or \(\systemmodel{PTAS}\), if for each \(\epsilon\), \(\epsilon>0\), there is a polynomial-time algorithm \(A\) that approximates \(f\) within ratio \(\epsilon\)~\cite{cj95-04-11}\@. % \apar{2-14} We say that a function \(g\) is \emph{\(\complexityclass{PSPACE}\)-hard} if \(\complexityclass{PSPACE}\subseteq\complexityclass{P}^g\), i.e., if every language in \(\complexityclass{PSPACE}\) is polynomial-time reducible to \(g\)\@. By ``approximating \(f\) within ratio \(\epsilon(n)\) is \(\complexityclass{PSPACE}\)-hard,'' we mean that, if \(g\) approximates \(f\) within ratio \(\epsilon(n)\), then \(g\) is \(\complexityclass{PSPACE}\)-hard\@. % \apar{2-15} Finally, we review some facts about algebraic techniques for encoding strings\@. We will use them to prove that \(\complexityclass{PCD}(\log n,q(n))=\complexityclass{GPCD}(\log n,q(n))\), which is Theorem~2 below\@. Let \(x\) be an element of \(\{0,1\}^n\)\@. The \emph{robust encoding} \(E_R(x)\) of \(x\) is an element of \(\{0,1\}^{2^n}\), indexed by elements \(v\) of \(\{0,1\}^n\), such that the \(v\)th bit of \(E_R(x)\) is \(\sum_{i=1}^n v_i x_i\bmod 2\)\@. Let \(l\) be \(\lceil\log n/\log\log n\rceil\) and \(p\) be a prime in the interval \([\log^{c}n,2\log^{c}n]\), where \(c\) is a constant determined in the proof of Lemma~1\@. Let \(I=\{1,2,\ldots,\lceil\log n\rceil\}\subset Z_p\)\@. Since \(\setsize{I^l}\geq n\), we can fix an injective map from \(\{0,1\}^n\) to the set of functions that map \(I^l\) to \(\{0,1\}\)\@. Regard \(x\) as one of these functions \(\funcspace{I^l}{\{0,1\}}\)\@. There exists an \(l\)-variable polynomial \(X\) over \(Z_p\), of degree at most \(l(\setsize{I}-1)\), that agrees with \(x\) on all \(\alpha\in I^l\)\@. The \emph{low-degree encoding} \(E_P(x)\) of \(x\) is any such function \(X\oftype\funcspace{Z_p^l}{Z_p}\)\@. Let \((y_1,y_2,\ldots,y_{p^l})\) denote \(E_P(x)\)\@. % \apar{2-16} The encoding \(E\) that is used in the proofs of Theorems 1 and 2 is given by the formula: \[E(x)\equiv(E_R(y_1),E_R(y_2),\ldots,E_R(y_{p^l}))\] \sentence Note that \(\setsize{E(x)}=\polyof(\strlnth{x})\)\@. % \apar{2-17} The following expression \(\Delta_{E'}\) is defined for every function \(E'\oftype\funcspace{S}{\Sigma^{n'}}\), every set \(S\), and every alphabet \(\Sigma\)\@. Typically, \(E'\) will be an error-correcting code, and \(\Delta_{E'}(y)\) measures the fraction of symbols of \(y\) that must be changed to transform \(y\) into a code word\@. Let \(y\) be an element of \(\Sigma^{n'}\)\@. Then \[\Delta_{E'}(y)\equiv\frac{\min_{x\in S}(\hamming(y,E'(x)))}{n'}\] where, if \(y_i=\sigma_{i1}\cdots \sigma_{in'}\), \(1\leq i\leq 2\), \(\sigma_{ij}\in\Sigma\), then \(\hamming(y_1,y_2)\) is the \emph{Hamming distance} between \(y_1\) and \(y_2\), i.e., the number of \(j\) for which \(\sigma_{1j}\neq\sigma_{2j}\)\@. Also, we define \(\Delta(y_1,y_2)\) as the fractional Hamming distance between \(y_1\) and \(y_2\), defined on pairs in which \(y_1\) and \(y_2\) have the same length\@. That is, \(\Delta(y_1,y_2)=\hamming(y_1,y_2)/n\) where \(\strlnth{y_1}=\strlnth{y_2}=n\)\@. % \asection{3}{Complexity-Theoretic Results} % \apar{3-1} Our first theorem on the language-recognition power of \(\systemmodel{PCDS}\)s addresses the question of whether verifiers that read \(\orderle{q(n)}\) rounds of the debate tape have more power than verifiers that read \(\orderle{q(n)}\) bits of the debate tape\@. Surprisingly, for \(r(n)=\orderge{\log n}\), the answer is no\@. This result relies heavily on the following fact about probabilistically checkable proofs\@. % \begin{alabsubtext}{Theorem}{1}{Arora et al.~\protect\cite{cj95-04-1}} % Let \(k\), \(n_1\), \(n_2,\ldots\), and \(n_k\) be integers and \(\varphi(x_1,x_2,\ldots,x_k)\) be an \(\complexityclass{NP}\) predicate, where \(\strlnth{x_i}=n_i\), for \(i=1,2,\allowbreak\ldots,k\)\@. Let \(n=\sum_{i=1}^k n_i\)\@. Then there exists a verifier \(V\) that uses \(\orderle{\log n}\) random bits and reads \(\orderle{k}\) bits of a proof \(\pi=(\pi_1,\pi_2,\ldots,\pi_k,y)\) of length \(\polyof(n)\) with the following properties: \begin{itemize} \item If \(\varphi(x_1,x_2,\ldots,x_k)=1\), there is a \(y\) such that, with probability 1,\linebreak[2] \(V\)~accepts\discretionary{}{}{} \(\pi=(E(x_1),E(x_2),\ldots,E(x_k),y)\)\@. \item For every \(\pi=(\pi_1,\ldots,\pi_k,y)\), if \(V\) accepts with probability greater than \(\frac{1}{2}\), then \(\varphi(E^{-1}(\pi_1),E^{-1}(\pi_2),\ldots,E^{-1}(\pi_k))=1\)\@. \end{itemize} \sentence % \end{alabsubtext} % \apar{3-2} In the next theorem, given an \(\complexityclass{NP}\) predicate \(\varphi\) of arity \(\Theta(q(n))\), we will need to refer to the string \(y\) whose existence is guaranteed by the first bullet above\@. Thus, we say \(y\) is a \emph{\(\complexityclass{PCP}(\log n,q(n))\) proof} for the predicate \(\varphi(x_1,x_2,\ldots,x_{\Theta(q(n))})\), and we refer to \(E(x_1),E(x_2),\ldots,E(x_{\Theta(q(n))})\) as the \emph{inputs} to the \(\complexityclass{PCP}(\log n,q(n)\)) proof \(y\)\@. % \begin{alabsubtext}{Theorem}{2}{} % For every \(q(n)\), \(\complexityclass{PCD}(\log n,q(n))=\complexityclass{GPCD}(\log n,q(n))\)\@. % \end{alabsubtext} % \begin{alabsubtext}{Proof of Theorem}{2}{} \prooffontshape % \apar{Proof of Theorem 2-1} The direction \(\complexityclass{PCD}(\log n,q(n))\subseteq \complexityclass{GPCD}(\log n,q(n))\) is immediate; we consider the other direction\@. Given a \(\systemmodel{GPCDS}\) \((D,V)\) with players \(1\) and \(0\), we construct an equivalent \(\systemmodel{PCDS}\) \((D',V')\) with players \(1'\) and \(0'\)\@. Suppose that \(D\) has \(N\) rounds on a given input and assume without loss of generality that \(N\) is even\@. Then \(D'\) has \(N+1\) rounds\@. Roughly, the idea is that in rounds \(1\) through \(N\), the players \(0'\) and \(1'\) play as in debate \(D\), except they encode their moves using the encoding \(E\) defined in Section~2\@. In round \(N+1\), player \(1'\) writes additional information, in order to convince \(V'\) that \(V\) would have accepted on the decoded debate in rounds \(1\) through \(N\), or that player \(0'\) has not properly encoded some of its moves\@. % \apar{Proof of Theorem 2-2} We first describe a strategy of player \(1'\) on input \(x\in L\) that causes \(V'\) to accept with probability \(1\)\@. Since \(x\in L\), there exists a strategy for \(1\) on \(x\) such that \(V\) accepts with probability 1\@. This induces the following strategy for \(1'\) in \(D'\) in the first \(N\) rounds\@. At the \(i\)th round, player \(1'\) first ``decodes'' each of the previous rounds \(1\) through \(i-1\)\@. Then, with respect to this sequence of moves, \(1'\) finds the move \(m\) that \(1\) would write in round \(i\) according to its winning strategy in \(D\)\@. Player \(1'\) plays \(E(m)\) in round \(i\)\@. Here, by ``decoding'' a given move, we mean finding the move \(M\) that minimizes the Hamming distance from \(E(M)\) to the given move\@. % \apar{Proof of Theorem 2-3} The string written by \(1'\) in round \(N+1\) is constructed so that \(V'\) can check that, for each random string \(R\) of \(V\), either \(V\) outputs \(1\) if it is given this random string and the decoded debate of rounds \(1,\ldots,N\) or that some move of \(0'\) read by \(V\) on random string \(R\) is a bad encoding\@. We say that a string \(y\) is a bad encoding if \(\Delta_E(y)>\epsilon\), where \(\epsilon>0\) is a parameter that is determined in Lemma~1 below, and \(\Delta_E(y)\) is as defined at the end of Section~2\@. Let \(V(R)\) denote the execution of verifier \(V\) with random string \(R\)\@. % \apar{Proof of Theorem 2-4} More precisely, the move of \(1'\) in round \(N+1\) contains the following strings\@. First, it contains the encoding of each move of player \(0'\)\@. Let \(x_i\) be the encoding of the move player \(0'\) in the \(i\)th round\@. Note that if, in round \(i\), player \(0'\) writes an encoding of a move of debate system \(D\), then \(x_i\) is the encoding of the encoding of a move in the debate system \(D\)\@. Second, it contains a \(\complexityclass{PCP}(\log n,1)\) proof \(\pi_{ij}\) for each bit of each move that \(0'\) played\@. The \((i,j)\)th of these proofs proves that the string encoded by \(1'\) has the same value as the \(j\)th bit of the \(i\)th move played by \(0'\)\@. (These proofs enable the verifier \(V'\) to check that \(1'\) properly encoded \(0'\)'s moves\@.) Note that all these proofs have as input only one string encoded by \(1'\) and one bit played by player \(0'\); therefore \(\complexityclass{PCP}(\log n,1)\) proofs exist, by Theorem~1\@. Lastly, for each random seed \(R\), the move of \(1'\) in round \(N+1\) contains a \(\complexityclass{PCP}(\log n,q(n))\) proof \(\pi_{R}\) that has one of the following properties: % \begin{itemize} \item when the moves played by \(1'\) and \(0'\) are decoded and used as the debate tape in \(D\), \(V(R)\) outputs \(1\), or \item at least one of the moves corresponding to moves of player \(0\) that \(V(R)\) reads is a bad encoding\@. \end{itemize} % The inputs to the above statement are \(\orderle{q}\) moves by \(1'\), corresponding to the \(\orderle{q}\) moves of player \(1\) read by \(V(R)\), and also the encoding of the moves of player \(0'\) that are in the last move of player \(1'\)\@. Observe that all the inputs are encoded by \(1'\)\@. Lemma~1 shows that the problem of recognizing a bad encoding is in \(\complexityclass{NP}\)\@. Thus, by Theorem~1, the \(\complexityclass{PCP}(\log n,q(n))\) proof needed in the second case exists\@. % \apar{Proof of Theorem 2-5} To summarize, in the last round player \(1'\) writes a string of the form \[((x_i)_i,(\pi_{ij})_{ij},(\pi_R)_R)\] where \(R\) ranges over random seeds of \(V\), \(i\in\{2,4,\ldots,N\}\) and \(j\in\{1,2,\ldots,l_i\}\), where \(l_i\) is the number of bits in the \(i\)th move of player \(0'\)\@. See Figure~1\@. % \begin{figure*} \begin{center} % \setlength{\unitlength}{0.04625em} \begin{picture}(777,830)(5,259) % \put(726,420){\makebox(0,0)[lb]{\raisebox{3pt}[0pt][0pt]{\(x_N\)}}} \put(726,700){\makebox(0,0)[lb]{\raisebox{3pt}[0pt][0pt]{\(x_2\)}}} \put(551,365){\makebox(0,0)[lb]{\raisebox{2pt}[0pt][0pt]{\small\(\pi_{23}\)}}} \put(421,365){\makebox(0,0)[lb]{\raisebox{2pt}[0pt][0pt]{\small\(\pi_{22}\)}}} \put(286,365){\makebox(0,0)[lb]{\raisebox{2pt}[0pt][0pt]{\small\(\pi_{21}\)}}} \put(321,325){\makebox(0,0)[lb]{\raisebox{2pt}[0pt][0pt]{\small\(\pi_{R_1}\)}}} \put(551,325){\makebox(0,0)[lb]{\raisebox{2pt}[0pt][0pt]{\small\(\pi_{R_2}\)}}} \put( 46,480){\makebox(0,0)[rb]{\raisebox{3pt}[0pt][0pt]{\(N-1\)}}} \put( 46,420){\makebox(0,0)[rb]{\raisebox{3pt}[0pt][0pt]{\(N\)}}} \put(166,340){\makebox(0,0)[rb]{\raisebox{3pt}[0pt][0pt]{\(N+1\)}}} \put( 46,580){\makebox(0,0)[rb]{\raisebox{3pt}[0pt][0pt]{\(4\)}}} \put( 46,640){\makebox(0,0)[rb]{\raisebox{3pt}[0pt][0pt]{\(3\)}}} \put( 46,700){\makebox(0,0)[rb]{\raisebox{3pt}[0pt][0pt]{\(2\)}}} \put( 46,760){\makebox(0,0)[rb]{\raisebox{3pt}[0pt][0pt]{\(1\)}}} \put(106,800){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\large\(D\)}}} \put(316,800){\makebox(0,0)[b]{\raisebox{0pt}[0pt][0pt]{\large\(D'\)}}} \put(726,580){\makebox(0,0)[lb]{\raisebox{3pt}[0pt][0pt]{\(x_4\)}}} \put(5,259){\placeepsinpic{35.7525em}{26.2811em}{c9504f1}} % \end{picture} \end{center} % \afigcap{1}{The debate transformation\@. Everything within the dashed contour is part of move \protect\(N+1\protect\) of \protect\(1'\protect\)\@.} % \end{figure*} % \apar{Proof of Theorem 2-6} Now we can describe the verifier \(V'\)\@. First \(V'\) chooses a random seed \(R\) and computes the indices \(i_1,\allowbreak i_2,\allowbreak\ldots,i_{q(n)}\) of rounds that \(V\) queries using the random seed \(R\)\@. It then probabilistically checks \(\pi_R\) with encoded inputs \(m_{i_k}\) for each even \(i_k\), and \(x_{i_k}\) for each odd \(i_k\), where \(m_i\) is the move in round \(i\)\@. Additionally, for all odd \(i_k\), \(V'\) chooses a \(j\in\{1,2,\ldots,l_{i_k}\}\) uniformly at random and probabilistically checks \(\pi_{i_kj}\) with input \(x_{i_k}\) and the \(j\) bit of \(m_{i_k}\)\@. % \apar{Proof of Theorem 2-7} Let us show that the debate system \((D',V')\) is a \(\systemmodel{PCDS}\) for \(L\) with error probability \(1-\frac{\epsilon}{2}\)\@. (Note that this implies the theorem since the error probability can be made less than \(\frac{1}{2}\) by repeating the verification a constant number of times in parallel\@.) % \apar{Proof of Theorem 2-8} In the case that \(x\in L\), it follows easily from the construction that \(V'\) accepts with probability \(1\), on the strategy for player \(1'\) described above\@. % \apar{Proof of Theorem 2-9} If \(x\notin L\), then \(0\) has a strategy such that \(V\) rejects with probability at least \(\frac{1}{2}\)\@. Consider the strategy for \(0'\) induced by this strategy of player \(0\) (defined in the same way as the induced strategy for player \(1'\) was defined for rounds \(1\) through \(N\))\@. Note that player \(0\) is declared the winner on input \(x\) for at least half of the random seeds \(R\)\@. Fix some such \(R\)\@. Then, one of two events must be true\@. The first is that the proof \(\pi_R\) causes the verifier \(V'\) to reject with probability at least \(\frac{1}{2}\) (by Theorem~1)\@. The second is that, for some \(i\) such that round \(i\) is read by \(V(R)\), the string \(x_i\) written by player \(1\) in round \(N+1\) is not the encoding of the string \(m\) actually played by \(0'\) in round \(i\), but of another string, say \(x\), where \(\Delta(x,m)>\epsilon\) (where \(\Delta\) is the fractional Hamming distance function defined at the end of Section~2)\@. % \apar{Proof of Theorem 2-10} Thus, with probability at least \(\epsilon\), \(V'\) chooses a \(j\) such that \(x_j\neq m_j\), and the proof \(\pi_{ij}\) causes \(V'\) to accept with probability at most \(\frac{1}{2}\)\@. Thus \(V'\) rejects in the second event with probability at least \(\frac{\epsilon}{2}\)\@. % {\nopagebreakbeginpar\markendlst{Proof of Theorem 2}} \end{alabsubtext} % \apar{3-3} We now prove a technical lemma that was used in the previous argument\@. % \begin{alabsubtext}{Lemma}{1}{} % For some \(\epsilon>0\), there exists a polynomial-time predicate \(F\) with the following property\@. For every \(y\), there exists a \(z\) such that \(F(y,z)=1\) if and only if \(\Delta_E(y)\geq \epsilon\)\@. % \end{alabsubtext} % \begin{alabsubtext}{Proof of Lemma}{1}{} \prooffontshape % \apar{Proof of Lemma 1-1} The code \(E\) is efficiently decodable in the following sense: There exists a polynomial-time computable function \(G\) such that, for every \(z,x\): \[\Delta(z,E(x))\leq\frac{1}{12}\logicimplies G(z)=x\] \sentence Let \(F(z)\) be the polynomial-time computable predicate \(\Delta(z,E(G(z)))>\frac{1}{12}\)\@. % \apar{Proof of Lemma 1-2} The decoding function \(G\) is constructed from the decoding functions for the two codes that \(E\) is composed of\@. Let \(z=(z_1,z_2,\ldots,z_{p^l})\)\@. First note that for each \(i\in\{1,2,\ldots,p^l\}\), we can find, by exhaustive search, \(y_i\) that minimizes \(\Delta(z_i,E_R(y_i))\), with ties broken arbitraily\@. This defines a function \(g\oftype\funcspace{Z_p^l}{Z_p}\)\@. % \apar{Proof of Lemma 1-3} It is easy to see that the multivariate polynomial self-corrector due to Gemmell and Sudan~\cite{cj95-04-12} can be used to construct a decoding function \(H\) such that, for every \(g,x\): % \begin{aequation}{1} \Delta(g,E_P(x))\leq\frac{1}{3}\logicimplies H(g)=x \end{aequation} \sentence % The self-corrector in~\cite{cj95-04-12} is randomized, but in our context it uses \(\orderle{\log n}\) random bits and can therefore be made deterministic at the expense of a polynomial factor in running time\@. % \apar{Proof of Lemma 1-4} Assume that \(\Delta_E(z)\leq\frac{1}{12}\)\@. Thus there exists \(x\) such that \(\Delta(z,E(x))<\frac{1}{12}\)\@. Let \(f\) be the multivariate polynomial \(E_P(x)\)\@. Note that, for every \(a\neq a'\), \(\Delta(E_R(a),E_R(a'))=\frac{1}{2}\)\@. This implies that for each \(i\) such that \(g(\alpha_i)\not=f(\alpha_i)\), \(\Delta(z_i,E_R(f(\alpha_i)))\geq\frac{1}{4}\)\@. Hence \(\Delta_E(z)\geq\frac{1}{4}\Delta(f,g)\)\@. Thus \(\Delta(f,g)\leq\frac{1}{3}\), and Equation~1 implies that \(H(g)=x\)\@. % {\nopagebreakbeginpar\markendlst{Proof of Lemma 1}} \end{alabsubtext} % \apar{3-4} If \(r(n)=\orderlt{\log n}\), then it is not necessarily true that \(\complexityclass{GPCD}(r(n),q(n))\subseteq \complexityclass{PCD}(r(n),q(n))\)\@. For example, it is clear that \(\complexityclass{GPCD}(0,1)\) is the entire polynomial-time hierarchy, whereas \(\complexityclass{PCD}(0,1)\) is just \(\complexityclass{P}\)\@. % \apar{3-5} We now turn to the proof of our main theorem: Every language in \(\complexityclass{PSPACE}\) is recognized by a debate system in which the verifier uses \(\orderle{\log n}\) random bits and reads \(\orderle{1}\) rounds (equivalently, by Theorem~2, \(\orderle{1}\) bits) of the debate\@. The following notation is used in the proof\@. Let \(\Phi=\exists x_1\forall x_2\ldots\exists x_n\phi(x_1,\ldots,x_n)\) be an instance of the problem (\(\problemset{QBF}\)); without loss of generality, we assume that quantifiers alternate strictly\@. This instance \(\Phi\) of \(\problemset{QBF}\) can be thought of as a game between two players, an ``existential'' player (player 1) who sets the odd-numbered variables, and a ``universal'' player (player 0) who sets the even-numbered variables\@. This view of the \(\problemset{QBF}\) problem as a game motivates the following definitions\@. The assignment tree \(A\) for \(\Phi\) is the complete binary tree of depth \(n\), where one edge from every internal node is labeled ``true'' and the other ``false\@.'' Each path \(P\) in the tree corresponds to an assignment of the variables; we say \(P\) satisfies \(\phi\) if this assignment satisfies \(\phi\)\@. Call edges at odd-numbered levels (that is, corresponding to existentially quantified variables) \(1\)-edges and edges at even-numbered levels \(0\)-edges\@. An \(\exists\)-strategy subtree \(A_1\) is a subtree of \(A\) that has two 0-edges from each node at each even level and one 1-edge from each node at each odd level\@. Similarly, a \(\forall\)-strategy subtree \(A_0\) is a subtree of \(A\) that has two 1-edges from each node at each odd level and one \(0\)-edge from each node at each even level\@. An \(\exists\)-strategy subtree \(A_1\) is \emph{optimal} if it maximizes (over all \(\exists\)-strategy subtrees) the number of paths that satisfy \(\phi\)\@. Similarly, a \(\forall\)-strategy subtree \(A_0\) is optimal if it maximizes (over all \(\forall\)-strategy subtrees) the number of paths that do not satisfy \(\phi\)\@. Note that if \(\Phi\in\problemset{QBF}\), all paths of an optimal \(\exists\)-strategy subtree satisfy \(\phi\), whereas if \(\Phi\notin\problemset{QBF}\), then no path of an optimal \(\forall\)-strategy subtree satisfies~\(\phi\)\@. % \apar{3-6} % \begin{alabsubtext}{Theorem}{3}{} % \(\complexityclass{PSPACE}=\complexityclass{GPCD}(\log n,1)\)\@. % \end{alabsubtext} % \begin{alabsubtext}{Proof of Theorem}{3}{} \prooffontshape % \apar{Proof of Theorem 3-1} The direction \(\complexityclass{GPCD}(\log n,1)\subseteq\complexityclass{PSPACE}\) is straightforward\@. To prove the other direction, we show that \(\problemset{QBF}\in\complexityclass{GPCD}(\log n,1)\)\@. Let \(\Phi=\exists x_1\forall x_2\ldots\exists x_n\phi(x_1,\ldots,x_n)\) be an instance of \(\problemset{QBF}\) in which quantifiers alternate strictly\@. Let \(A_0\), \(A_1\) be optimal \(\forall\)- and \(\exists\)-strategy subtrees of \(\Phi\), respectively\@. Note that \(\Phi\in\problemset{QBF}\) if and only if the unique path \(P\) of length \(n\) that is in both \(A_0\) and \(A_1\) satisfies~\(\phi\)\@. % \apar{Proof of Theorem 3-2} We give a debate format and a protocol of players \(0\) and \(1\) that enable the players to record parts of the strategy subtrees \(A_0\) and \(A_1\) in such a way that a verifier can efficiently check whether or not path \(P\) satisfies~\(\phi\)\@. % \apar{Proof of Theorem 3-3} In the debate, the players alternately play rounds, starting with player \(1\)\@. Roughly, in one round, player \(i\) does two things: presents a challenge to player \(1-i\) and responds to previous challenges written by player \(1-i\)\@. A \emph{challenge} by player \(1-i\) to player \(i\) is simply a path of the strategy subtree \(A_i\) that ends in a \((1-i)\)-edge\@. The \emph{response} of player \(i\) to this challenge is the edge that extends this path in \(A_i\) (if the path is not already of length \(n\))\@. % \apar{Proof of Theorem 3-4} Note that a challenge \emph{to} player \(1\) (respectively~\(0\)) has to be a path of \(A_1\) (respectively~\(A_0\))\@. How can player \(0\) write down such a path \emph{without knowing} \(A_1\)\@? Essentially, in round \(t\), player \(0\) must present paths that are consistent with what player \(1\) wrote in rounds \(1\) through \(t-1\)\@. We will elaborate on this point below\@. % \apar{Proof of Theorem 3-5} Play proceeds as follows: In round \(t\), one of the players writes a tree \(T_t\)\@. If player \(i\) is honest, then in round \(t\equiv i\bmod 2\), player \(i\) writes the (unique) smallest subtree \(T_t\) of \(A_i\) such that \(T_t\) contains all challenges by player \(1-i\) at rounds \(j4n\); this will ensure that the error probability is no more than \(2(n-1)/(g-3)\), as explained below\@. We let \(f(n)\), the length of a round, be such that every binary tree of depth at most \(n\) with at most \(g(n)\) leaves can be described using \(f(n)\) bits, via some simple encoding of trees to strings\@. This is sufficient, since the number of leaves of \(T_{g(n)}\) is at most \(g(n)\)\@. % \apar{Proof of Theorem 3-10} Below, we state \(V\)'s algorithm formally and prove it correct, but first we explain intuitively how \(V\) can catch a cheating player by examining only a constant number of rounds of the debate\@. Suppose that the input formula is true and hence that player \(1\) follows the protocol honestly\@. If they are valid, the trees \(T_g\) (player \(1\)'s last move) and \(T_{g-1}\) (player \(0\)'s last move) intersect in a unique path, say \(P(g)\)\@. If it is of length \(n\), then \(P(g)\) satisfies \(\phi\), and \(V\) will certainly declare player \(1\) the winner\@. Thus player \(0\) must try to ``stall'' and prevent \(P(g)\) from growing to length \(n\)\@. Consider a move \(T_t\), where \(t\setsize{P(t-1)}\)\@. Player \(0\) can cooperate in fewer than \(n\) rounds, or else \(P(g)\) is of length \(n\)\@. Essentially, our formal proof shows that, if player \(0\) indeed cooperates in fewer than \(n\) rounds, then many intermediate moves \(T_t\) are either invalid or not subtrees of the final move \(T_{g-1}\)\@. Either way, \(V\) can detect with constant probability that player \(0\) is cheating by examining only a constant number of randomly chosen moves\@. % \apar{Proof of Theorem 3-11} We now give a formal statement of \(V\)'s algorithm and a proof of its correctness\@. Verifier \(V\) first examines the last subtrees, \(T_{g-1}\) and \(T_g\), written by players \(0\) and \(1\) respectively\@. If \(T_{g-1}\) is not valid, \(V\) accepts; if \(T_g\) is not valid, \(V\) rejects\@. Otherwise, let \(P(g)\) be the (unique) path in both \(T_{g-1}\) and \(T_g\)\@. If the length of \(P(g)\) is \(n\) and \(P(g)\) satisfies \(\phi\), \(V\) accepts\@. If the length of \(P(g)\) is \(n\) and \(P(g)\) does not satisfy \(\phi\), then \(V\) rejects\@. % \apar{Proof of Theorem 3-12} Otherwise, the length of \(P(g)\) is less than \(n\)\@. In this case, \(V\) chooses a random round \(t\), \(1p(j)\) for all \(jp(t-1)\ge p(j)\), as required\@. % {\nopagebreakbeginpar\markendlst{Proof of Theorem 3}} \end{alabsubtext} % Combining Theorem~3 with Theorem~2, we obtain the following result\@. % \begin{alabsubtext}{Corollary}{1}{} % \(\complexityclass{PSPACE}=\complexityclass{PCD}(\log n,1)\)\@. % \end{alabsubtext} % \apar{3-7} We can also obtain a characterization of debate systems that allow ``zero-sided'' error\@. Let a \(\systemmodel{ZPCDS}\) be a \(\systemmodel{PCDS}\) for which the verifier returns one of the three possibilities ``player \(1\) wins,'' ``player \(0\) wins,'' and ``I don't know who wins,'' in which the verifier is always right in the first two cases, and the probability of the third case is at most \(\epsilon<\frac{1}{2}\)\@. % \begin{alabsubtext}{Corollary}{2}{} % \(\complexityclass{PSPACE}=\complexityclass{ZPCD}(\log n,1)\)\@. % \end{alabsubtext} % \begin{alabsubtext}{Proof of Corollary}{2}{} \prooffontshape % This follows from the fact that \(\complexityclass{PSPACE}\) is closed under complement\@. Given an \(L\in\complexityclass{PSPACE}\), our main result shows that \(L\) and the complement of \(L\) have one-sided \(\systemmodel{PCDS}\)s \((D,V)\) and \((\overline{D},\overline{V})\), respectively, with error probability \(\frac{1}{2}\)\@. Now consider the debate in which both \(D\) and \(\overline{D}\) are performed, and the verifier declares \(0\) the winner if \(V\) rejects, declares \(1\) the winner if \(\overline{V}\) rejects, and otherwise says that it does not know the winner\@. It is easy to see that this verifier will have zero-sided error and will declare a winner with probability at least \(\frac{1}{2}\)\@. % {\nopagebreakbeginpar\markendlst{Proof of Corollary 2}} \end{alabsubtext} % \asection{4}{\ifx\customsecstyle\undeftex\else\customsecstyle\fi Functions that are \protect\(\complexityclass{PSPACE}\protect\)-Hard to~Approximate\discretionary{}{}{}} % \apar{4-1} In this section, we give many examples of \(\complexityclass{PSPACE}\)-hard functions that are hard to approximate\@. We consider maximization versions of the problem of deciding whether a quantified Boolean formula is true and show that one version can be approximated within a ratio of \(\frac{1}{2}\), yet there is some constant \(\epsilon<1\) such that approximating the function within a ratio of \(\epsilon\) is \(\complexityclass{PSPACE}\)-hard\@. We prove even stronger results for the maximization versions of several other \(\complexityclass{PSPACE}\)-complete problems\@. For example, there is a constant \(\epsilon>0\) such that approximating Finite Automata Intersection (cf.~Kozen~\cite{cj95-04-16}) and Generalized Geography (cf.~Schaefer~\cite{cj95-04-21}) within ratio \(n^\epsilon\) is \(\complexityclass{PSPACE}\)-hard\@. % \apar{4-2} We first consider variants of a well-known \(\complexityclass{PSPACE}\)-complete problem, that of deciding whether a quantified Boolean formula is satisfiable\@. In what follows, we consider quantified (Boolean) formulas in CNF (conjunctive normal form); that is, quantified formulas of the form: \[\Phi=Q_1 x_1 Q_2 x_2\ldots Q_n x_n\phi(x_1,x_2,\ldots,x_n)\] where each \(Q_i\in\{\exists,\forall\}\), each \(x_i\) is a Boolean variable, and \(\phi\) is in conjunctive normal form\@. If each clause of \(\phi\) has exactly three literals, we say the quantified formula is in \(\inputset{3CNF}\)\@. Let \(\problemset{QSAT}\) and \(\problemset{Q3SAT}\) be the sets of satisfiable quantified formulas in \(\inputset{CNF}\) and \(\inputset{3CNF}\), respectively\@. % \apar{4-3} Suppose that the variables of the formula are chosen, in order of quantification, by two players \(0\) and \(1\), where player \(0\) chooses the universally quantified variables and player \(1\) chooses the existentially quantified variables\@. If player \(1\) can guarantee that \(k\) clauses of \(\phi\) will be satisfied by the resulting assignment, regardless of what player \(0\) chooses, we say that \(k\) clauses of \(\Phi\) are \emph{simultaneously satisfiable}\@. We let \(\problemfunc{MAX-QSAT}\) (respectively \(\problemfunc{MAX-Q3SAT}\)) be the function whose domain is the set of quantified formulas that maps a quantified formula (respectively quantified \(\inputset{3CNF}\) formula) \(\Phi\) to the maximum number of simultaneously satisfiable clauses\@. The results in \cite{cj95-04-1} and \cite{cj95-04-2} show that \(\problemfunc{MAX-QSAT}\) is \(\complexityclass{NP}\)-hard to approximate within certain ratios\@. % \begin{alabsubtext}{Theorem}{4}{} % There is a constant \(0<\epsilon<1\) such that approximating \(\problemfunc{MAX-Q3SAT}\) within ratio \(\epsilon\) is \(\complexityclass{PSPACE}\)-hard\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % \end{alabsubtext} % \begin{alabsubtext}{Proof of Theorem}{4}{} \prooffontshape % \apar{Proof of Theorem 4-1} Let \(L\) be a language in \(\complexityclass{PSPACE}\)\@. We showed in Section~3 that \(L\) is in \(\complexityclass{PCD}(\log n,1)\)\@. We reduce the problem of deciding whether a string \(x\) is in \(L\) to the problem of approximating the number of simultaneously satisfiable assignments of a quantified \(\inputset{3CNF}\) formula\@. % \apar{Proof of Theorem 4-2} Let \((D,V)\) be a \(\systemmodel{PCDS}\) for \(L\), where \(V\) is polynomial-time bounded and uses \(r(n)=\orderle{\log n}\) random bits and \(\orderle{1}\) queries\@. Let \(D=(f(n),g(n))\)\@. Without loss of generality, we can assume that \(f(n)\) and \(g(n)\) are polynomials\@. % \apar{Proof of Theorem 4-3} Given an instance \(x\) of \(L\), say of length \(n\), we construct a quantified formula from \((D,V)\) as follows\@. There are \(f(n)g(n)\) ordered variables, one for each bit of a debate corresponding to the debate format\@. The first \(f(n)\) variables, which correspond to the first round of a debate, are existentially quantified, the next \(f(n)\) variables, which correspond to the second round, are universally quantified, and so on\@. % \apar{Proof of Theorem 4-4} For each sequence of random bits \(R\) of length \(r(n)\), there is a subformula with \(s=\orderle{1}\) clauses, with variables corresponding to the bits of a debate that are queried on random sequence \(R\)\@. The subformula is satisfied by a truth assignment to the variables if and only if the verifier outputs \(1\), when the query bits are as in the truth assignment\@. % \apar{Proof of Theorem 4-5} If \(x\) is accepted by \((D,V)\), then there exists a debate subtree such that, on each debate (or path of the tree), \(V\) outputs \(1\) on all of the random strings\@. Thus, player \(1\) can choose the values of the existential variables so that all clauses of the subformulas are simultaneously satisfiable\@. % \apar{Proof of Theorem 4-6} If the input \(x\) is not accepted by \((D,V)\), then in every debate subtree, there is a debate on which \(V\) outputs \(1\) on at most \(\frac{1}{2}\) of the random strings\@. Thus, no matter what truth assignment player \(1\) chooses for the existential variables, there is a choice for the universal variables such that at most \(\frac{1}{2}\) of the subformulas are satisfied\@. Hence, at most \(\frac{1}{2}\) of the subformulas are simultaneously satisfiable\@. Since each subformula contains \(\orderle{1}\) clauses, it follows that at most a constant fraction \(<1\) of the clauses are simultaneously satisfiable\@. % {\nopagebreakbeginpar\markendlst{Proof of Theorem 4}} \end{alabsubtext} % \apar{4-4} Let \(\problemfunc{\((\log n)\)-MAX-Q-FORMULA}\) be the function whose domain is the set of quantified formulas in which the ``clauses'' are general formulas with at most \(\log n\) variables instead of being in \(\inputset{CNF}\)\@. The above result can be extended to prove the following\@. % \begin{alabsubtext}{Theorem}{5}{} % There is a constant \(0<\epsilon<1\) such that approximating \(\problemfunc{\((\log n)\)-MAX-Q-FORMULA}\) within ratio \(n^{\epsilon}\) is \(\complexityclass{PSPACE}\)-hard\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % \end{alabsubtext} % \begin{alabsubtext}{Proof of Theorem}{5}{} \prooffontshape Use standard pseudorandom sampling techniques \mbox{\cite{cj95-04-5,cj95-04-14}}\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % {\nopagebreakbeginpar\markendlst{}} \end{alabsubtext} % \apar{4-5} We next consider a variant of \(\problemset{Q3SAT}\) called \emph{Balanced \(\problemset{Q3SAT}\)} (\(\problemset{QB3SAT}\))\@. We say a quantified formula is balanced if every clause of the formula contains some existentially quantified variable\@. Balanced \(\problemset{Q3SAT}\) consists of those true quantified formulas in \(\inputset{3CNF}\) form that are also balanced\@. This language is easily seen to be \(\complexityclass{PSPACE}\)-complete, by the following reduction from \(\problemset{Q3SAT}\)\@. An instance \[Q_1 x_1 Q_2 x_2\ldots Q_n x_n\phi(x_1,x_2,\ldots,x_n)\] of \(\problemfunc{MAX-QSAT}\), where \(\phi\) has \(m\) clauses, is mapped to the instance \[ Q_1 x_1 Q_2 x_2\ldots Q_n x_n\exists w_1\ldots\exists w_m \phi'(x_1,x_2,\ldots,x_n,w_1,\ldots,w_m) \] where \(\phi'\) is obtained from \(\phi\) by replacing each clause \(C_j=(l_1\logicor l_2\logicor l_3)\) of \(\phi\) by the two clauses \((w_j\logicor l_1\logicor l_2)\) and \((\bar{w_j}\logicor l_3\logicor l_3)\), \(1\le j\le m\)\@. % \apar{4-6} We define the corresponding function \(\problemfunc{MAX-QB3SAT}\) to be the function \(\problemfunc{MAX-Q3SAT}\), restricted to the domain of balanced quantified formulas\@. This provides an example of a function that \emph{can} be approximated to within some constant ratio but \emph{cannot} be approximated to within an arbitrary constant ratio, unless \(\complexityclass{PSPACE}=\complexityclass{P}\)\@. % \begin{alabsubtext}{Lemma}{2}{} % There is a polynomial-time algorithm that approximates \(\problemfunc{MAX-QB3SAT}\) within ratio \(\frac{1}{2}\)\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % \end{alabsubtext} % \begin{alabsubtext}{Proof of Lemma}{2}{} \prooffontshape % \apar{Proof of Lemma 2-1} Let \(\Phi=Q_1 x_1\ldots Q_n x_n\phi(x_1,\ldots,x_n)\) be a balanced quantified formula in \(\inputset{3CNF}\)\@. Let \(\phi'\) be the formula obtained from \(\phi\) by eliminating all universally quantified variables\@. Since \(\phi\) is balanced, note that the number of clauses of \(\phi'\) is equal to the number of clauses of \(\phi\) (however, clauses may now have only one literal)\@. % \apar{Proof of Lemma 2-2} Johnson~\cite{cj95-04-15} showed that a truth assignment to the variables of \(\phi'\) that satisfies at least \(\frac{1}{2}\) of the clauses can be found in polynomial time\@. Player \(1\) can use this assignment to ensure that at least \(\frac{1}{2}\) of the clauses of \(\phi\) are satisfied, no matter what the values of the universally quantified variables are\@. % {\nopagebreakbeginpar\markendlst{Proof of Lemma 2}} \end{alabsubtext} % \begin{alabsubtext}{Lemma}{3}{} % There is a constant \(0<\epsilon<1\) such that approximating \(\problemfunc{MAX-QB3SAT}\) within ratio \(\epsilon\) is \(\complexityclass{PSPACE}\)-hard\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % \end{alabsubtext} % \begin{alabsubtext}{Proof of Lemma}{3}{} \prooffontshape % In Theorem~4, we reduced the problem of deciding whether an input \(x\) is accepted by a \(\systemmodel{PCDS}\) \((D,V)\) to the problem of approximating a quantified formula \(\Phi\)\@. The formula \(\Phi\) can be converted into a balanced subformula as described in the discussion preceding Lemma~2\@. It is straightforward to show that the resulting balanced quantified formula \(\Phi'\) also has the property that, if \(x\) is accepted by \((D,V)\), then all clauses of \(\Phi'\) are simultaneously satisfiable, but if \(x\) is not accepted, at most a constant fraction \(<1\) are simultaneously satisfiable\@. % {\nopagebreakbeginpar\markendlst{Proof of Lemma 3}} \end{alabsubtext} % \apar{4-7} We next consider a problem from automata theory\@. Let \(\problemset{FA-INT}\) be the set of sequences \(A_1,\allowbreak A_2,\allowbreak\ldots,A_m\) of deterministic finite-state automata having the same input alphabet \(\Sigma\) such that there exists a string \(w\) that is accepted by all the automata\@. Kozen~\cite{cj95-04-16} showed the problem to be \(\complexityclass{PSPACE}\)-complete\@. % \apar{4-8} The function \(\problemfunc{MAX-FA-INT}\) has as its domain the set of all sequences \(A_1,\allowbreak A_2,\allowbreak\ldots,A_m\) of deterministic finite-state automata having the same input alphabet \(\Sigma\), and maps the sequence to the largest number \(k\) such that there exists a string \(w\) that is accepted by \(k\) of the automata\@. We prove a non-approximability result for \(\problemfunc{MAX-FA-INT}\)\@. % \begin{alabsubtext}{Theorem}{6}{} % There is a constant \(0<\epsilon<1\) such that approximating \(\problemfunc{MAX-FA-INT}\) within ratio \(n^\epsilon\) is \(\complexityclass{PSPACE}\)-hard\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % \end{alabsubtext} % \begin{alabsubtext}{Proof of Theorem}{6}{} \prooffontshape % \apar{Proof of Theorem 6-1} We describe a reduction from a new variant of \(\problemfunc{MAX-Q3SAT}\)\@. The function \(\problemfunc{MAX-FIX-QSAT}\) differs from \(\problemfunc{MAX-Q3SAT}\) in two ways\@. First, the domain is the set of quantified formulas, where the ``clauses'' are now the conjunction of \(\orderle{\log n}\) ``subclauses,'' each the disjunction of three literals\@. Second, given an instance of this domain, the function outputs the maximum size \(k\) of a set of clauses that player \(1\) can guarantee will be satisfied, regardless of what assignment player \(0\) chooses for the universal variables\@. Thus for \(\problemfunc{MAX-FIX-QSAT}\), the set of \(k\) satisfied clauses must be fixed in advance, that is, the set must be the same for all assignments of player \(0\)\@. However, for \(\problemfunc{MAX-Q3SAT}\), the set of \(k\) simultaneously satisfied clauses may depend on the assignments of player \(0\)\@. The proof of Theorem~4 can be extended to show that there is some constant \(\epsilon>0\) such that approximating \(\problemfunc{MAX-FIX-QSAT}\) to within ratio \(n^\epsilon\) is \(\complexityclass{PSPACE}\)-hard\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % \apar{Proof of Theorem 6-2} We now describe our reduction from \(\problemfunc{MAX-FIX-QSAT}\) to \(\problemfunc{MAX-FA-INT}\) such that an instance of \(\problemfunc{MAX-FIX-QSAT}\) has a set of \(k\) clauses that player \(1\) can guarantee will be satisfied, if and only if the instance of \(\problemfunc{MAX-FA-INT}\) has \(k\) automata that accept the same string\@. Let \[\Phi=Q_1 x_1 Q_2 x_2\ldots Q_n x_n\phi(x_1,x_2,\ldots,x_n)\] be an instance of \(\problemfunc{MAX-FIX-QSAT}\), where \(\phi\) has \(m\) clauses\@. Moreover, assume without loss of generality that each variable appears in some clause\@. % \apar{Proof of Theorem 6-3} We first describe a set \(\problemset{Valid}\) of strings \(w\); roughly, each string in this set describes possible choices of player \(1\) for the existentially quantified variables, against all possible choices of player \(0\) for the universally quantified variables\@. We will later construct \(m\) sets of automata, one set per clause, such that all automata in each of \(k\) sets accept some string \(w\), which happens to lie in the set \(\problemset{Valid}\), if and only if the quantified formula \(\Phi\) has \(k\) simultaneously satisfiable clauses\@. % \apar{Proof of Theorem 6-4} Each string \(w\) in the set \(\problemset{Valid}\) is of the form \(\$w_1\$w_2\$\ldots\$w_N\$\), where each \(w_i=w_{i1}w_{i2}\ldots w_{in}\) is a binary string of length \(n\), corresponding to a truth assignment to the variables of \(\phi\), and \(N=2^u\), where \(u\) is the number of universally quantified variables in \(\Phi\)\@. Moreover, \(w\) must have properties (1), (2), and (3) below\@. % \apar{Proof of Theorem 6-5} Roughly, these properties are necessary and sufficient to ensure that \(w\) is in \(\problemset{Valid}\) if and only if the strings \(w_i\) correspond to paths of an \(\exists\)-assignment subtree that describes the assignments of player \(1\) against all possible assignments of player \(0\) (as explained in the paragraph preceding Theorem~3)\@. Note that such a tree has \(N\) leaves\@. Moreover, these paths are enumerated in order, from left to right of the assignment subtree\@. We now list the three properties\@. % \begin{enumerate} \item[1.] Suppose that \(x_j\) is universally quantified\@. Then, \(w_{1j}=0\) and \(w_{Nj}=1\)\@. Moreover, if \(w_i\) is such that \(w_{ij}=1\) for all \(j\) such that \(x_j\) is universally quantified, then \(i=N\)\@. \item[2.] Suppose that \(x_j\) is universally quantified and \(i>1\)\@. Then, \(w_{ij}=\bar{w}_{i-1,j}\) if for all \(j'>j\) such that \(x_{j'}\) is universally quantified, \(w_{i-1,j'}=1\), and \(w_{ij}=w_{i-1,j}\) otherwise\@. \item[3.] Suppose that \(x_j\) is existentially quantified and \(i>1\)\@. Then, \(w_{ij}=w_{i-1,j}\), unless for all \(j'>j\) such that \(x_{j'}\) is universally quantified, \(w_{i-1,j'}=1\)\@. In the latter case, there is no restriction on \(w_{ij}\)\@. \end{enumerate} % We say \(w\) is not valid at index \(j\), if property (2) or (3) fails for \(j\)\@. % \apar{Proof of Theorem 6-6} We consider two types of automata: ``syntax checking'' automata and ``clause checking'' automata\@. We will later use these automata to construct the automata that are used in the \(\problemfunc{MAX-FA-INT}\) instance\@. For \(1\le j\le n\), automaton \(S_j\) checks that the \(j\)th bit of each \(w_i\) has the property (2) or (3) above, depending on whether \(j\) is universally or existentially quantified\@. Automaton \(S_{n+1}\) checks that the \(\$\)s are separated by strings of length exactly \(n\), and that property (1) above holds\@. Clearly, a string is accepted by all \(n+1\) of the automata if and only if it is in the set \(\problemset{Valid}\)\@. Moreover, each of these automata can be constructed to have \(\polyof(n)\) states\@. % \apar{Proof of Theorem 6-7} There are \(m\) clause-checking automata \(C_1,\ldots,C_m\), each with \(\polyof(n)\) states, such that a string \(w\in\problemset{Valid}\) is accepted by \(C_j\) if and only if on all paths of the corresponding assignment subtree, the \(j\)th clause is satisfied\@. % \apar{Proof of Theorem 6-8} We now construct \(m\) automata\@. The \(i\)th automaton \(A_i\) does the following checks on its input string\@. % \begin{enumerate} \item[1.] Perform the check done by automaton \(S_{n+1}\)\@. \item[2.] If \(x_j\) or \(\bar{x}_j\) is a literal of \(C_i\), then perform the check of \(S_j\)\@. (In this case, say that \(A_i\) \emph{examines} bit \(x_j\)\@.) \item[3.] Perform the check done by automaton \(C_i\)\@. \end{enumerate} % Check (2) can be done by an automaton with \(\polyof(n)\) states\@. Roughly, for each \(i\), the automaton stores the the bits \(w_{i-1,j}\) and \(w_{ij}\), where bit \(x_j\) is examined by \(C_i\)\@. Also, the position of the rightmost universal index with value \(0\) in \(w_i\) is stored\@. This information is sufficient to perform the check of \(S_j\) on the string \(w_i\)\@. Since \(A_i\) performs the checks of three automata of size \(\polyof(n)\), \(A_i\) is also of size \(\polyof(n)\)\@. % \apar{Proof of Theorem 6-9} If player \(1\) can guarantee that a fixed set of \(k\) clauses of \(\phi\) are satisfied for all assignments of player \(0\), then there is a corresponding string \(w\) that is accepted by \(k\) automata\@. % \apar{Proof of Theorem 6-10} Conversely, suppose that \(k>0\) automata all accept some string \(w\)\@. Note that \(w\) may not be a member of \(\problemset{Valid}\)\@. However, \(w\) must pass check (1), because \(k>0\)\@. Hence, suppose that \(w\) is not valid at \(I\) indices\@. We prove by induction on \(I\) that there exists a string \(w'\) in \(\problemset{Valid}\) such \(k\) automata accept \(w'\)\@. From this it follows that there is a set of \(k\) clauses of \(\Phi\) that player \(1\) can guarantee will be satisfied\@. % \apar{Proof of Theorem 6-11} The base case, when \(I=0\), is immediate, for in that case \(w=w'\)\@. Suppose \(I>0\), and let \(j\) be the smallest invalid index\@. In what follows, if \(x_j\) is existentially (universally) quantified, we say that \(j\) is an existential (universal) index\@. % \apar{Proof of Theorem 6-12} If \(j\) is an existential index, we define \(w_i'\) as follows for \(1\le i \le N\): Let \(w_{ij}'=0\) and let \(w_{is}'=w_{is}\) for \(s\neq j\)\@. The resulting string has \(I-1\) invalid indices\@. Furthermore, it is still accepted by \(k\) automata\@. (This is because none of the \(k\) accepting automata can possibly examine bit \(j\)\@.) We can now apply induction to complete the proof\@. % \apar{Proof of Theorem 6-13} Next, suppose that \(j\) is a universal index\@. The procedure to construct \(w'\) from \(w\) is more complicated in this case\@. We do it in stages\@. For each set of bits \(b_1\ldots b_{j-1}\), we consider separately the (unique) longest contiguous substring \(w_r\$\ldots\$w_{r'}\$\) of \(w\) (if any) such that \(b_1\ldots b_{j-1}\) is a prefix of each \(w_i\), \(r\le i\le r'\)\@. Call this substring \(w[b_1\ldots b_{j-1}]\)\@. In the next paragraph, we describe a new substring \(w'[b_1\ldots b_{j-1}]\) that is obtained from \(w[b_1\ldots b_{j-1}]\)\@. We then let \(w'\) be the string obtained by concatenating the substrings \(w'[b_1\ldots b_{j-1}]\) in the appropriate order\@. Our construction ensures that \(w'\) has \(I-1\) invalid indices and is accepted by all \(k\) automata that accept \(w\)\@. % \apar{Proof of Theorem 6-14} Therefore, fix \(b_1\ldots b_{j-1}\), and consider only the substring \(w_{r}\$\ldots\$w_{r'}\$\)\@. Note that, for all universal indices \(j'>j\), \(w_{rj'}=0\) if \(j'\) is valid, and \(w_{r'j'}=1\)\@. (If this were not the case, it would contradict the facts that \(1\ldots j-1\) are valid indices and that \(w_r\$\ldots\$w_{r'}\$\) is the longest substring of \(w\) such that \(b_1\ldots b_{j-1}\) is a prefix of each \(w_i\)\@.) Let \(l\) be the smallest number such that, for all universal indices \(j'>j\), \(w_{lj'}=1\)\@. % \apar{Proof of Theorem 6-15} Let \(w'_r\$\ldots\$w'_l\$\) be such that, for \(1\le i\le l\), \(w'_{ij}=0\), and, for \(s\neq j\), \(w'_{is}=w_{is}\)\@. Similarly, let \(w''_{r}\$\ldots\$w''_l\$\) be such that, for \(1\le i\le l\), \(w''_{ij}=1\) and, for \(s\neq j\), \(w''_{is}=w_{is}\)\@. % \apar{Proof of Theorem 6-16} Then, the new string \(w'[b_1\ldots b_{j-1}]\) is \(w'_{r}\$\ldots\$w'_l\$ w''_{r}\$\ldots\$ w''_l\$\)\@. % \apar{Proof of Theorem 6-17} This completes the description of \(w'\)\@. The construction guarantees that (i) \(w'\) has \(I-1\) invalid indices (namely, those invalid indices \(j'>j\) of \(w\)) and (ii) \(w'\) is accepted by the \(k\) automata that accept \(w\)\@. Again, induction can be applied to complete the proof\@. % {\nopagebreakbeginpar\markendlst{Proof of Theorem 6}} \end{alabsubtext} % \apar{4-9} Generalized Geography is an abstraction of a popular car game in which two players alternately list the names of countries, each beginning with the last letter of the previous country, until one player cannot list a new country\@. A corresponding game can be played on a directed graph \(G\) that has a distinguished start node \(s\)\@. A marker is initially placed on \(s\), and two players, \(0\) and \(1\), alternately move it along an edge, with the constraint that player \(1\) starts and each edge can be used only once\@. The first player unable to move loses\@. Schaefer~\cite{cj95-04-21} defines \(\problemset{GGEOG}\) to be the set of pairs \((G,s)\) such that player \(1\) has a winning strategy\@. % \apar{4-10} Informally, a natural optimization version of \(\problemset{GGEOG}\) is to compute how long player \(1\) can keep the game going, even if player \(1\) does not eventually win the game\@. We say \((G,s)\) can be played for \(k\) rounds if player \(1\) has a strategy that causes the marker to move along \(k\) edges of the graph before the game ends\@. We define \(\problemset{MAX-GGEOG}\) to be the function whose domain is the set of pairs \((G,s)\), where \(G\) is a directed graph with node \(s\), that maps a pair \((G,s)\) to the maximum number \(k\) of rounds that \((G,s)\) can be played\@. % \begin{alabsubtext}{Theorem}{7}{} % There is a constant \(0<\epsilon<1\) such that it is \(\complexityclass{PSPACE}\)-hard to approximate \(\problemfunc{MAX-GGEOG}\) within ratio \(n^\epsilon\)\@. % \end{alabsubtext} % \begin{alabsubtext}{Proof of Theorem}{7}{} \prooffontshape % \apar{Proof of Theorem 7-1} We first modify Schaefer's reduction~\cite{cj95-04-21} to obtain a reduction from \(\problemfunc{MAX-Q3SAT}\) to \(\problemfunc{MAX-GGEOG}\)\@. We later describe a simple modification of our construction, to obtain a reduction from \(\problemfunc{\((\log n)\)-MAX-Q-FORMULA}\) to \(\problemfunc{MAX-GGEOG}\)\@. \ifx\customparstyle\undeftex\else\customparstyle\fi % \apar{Proof of Theorem 7-2} Let \(\Phi=Q_1 x_1 Q_2 x_2\ldots Q_n x_n\phi(x_1,\ldots,x_n)\) be an instance of \(\problemfunc{MAX-Q3SAT}\), where \(\phi\) contains \(m\) clauses\@. In what follows, we assume that \(n\) is even and that \(Q_n=\forall\); the reduction can easily be modified to handle the other cases\@. % \apar{Proof of Theorem 7-3} We construct from \(\Phi\) an instance \((G,s)\) of \(\problemfunc{MAX-GGEOG}\) such that, if a maximum of \(k\) clauses of \(\Phi\) are simultaneously satisfiable, then \((G,s)\) can be played for a maximum of \(4n+kn^2+\orderle{1}\) steps\@. From this property, it follows that, given an approximate value for the length of the generalized geography game, an approximate value for the number of satisfiable clauses can be deduced\@. The graph \(G\) is composed of a ``variable-setting'' component, a ``clause-testing'' component and a ``line\@.'' We describe each of these components in turn and also describe how they are interconnected\@. % \apar{Proof of Theorem 7-4} We first describe the variable-setting component\@. The node set is: \[ \begin{array}{rcl} V_1 & = & \setof{x_i,\bar{x}_i,u_i,v_i}{Q_i=\exists,1\le i\le n} \\ & \setunion & \setof{x_i,\bar{x}_i,u_i,v_i,w_i,\bar{w}_i,z_i}{Q_i=\forall,1\le i\le n} \\ & \setunion & \{u_{n+1}\} \end{array} \] \sentence % \apar{Proof of Theorem 7-5} Node \(u_1\) is the start node \(s\)\@. The nodes \(x_i,\bar{x}_i,1\le i\le n\) are referred to below as ``literal'' nodes\@. The edge set is: \[ \ifx\customstretcha\undeftex\else% \renewcommand{\arraystretch}{\customstretcha}% \fi \begin{array}{rcl} E_1 & = & \setof{(u_i, x_i),(u_i,\bar{x}_i),(x_i,v_i),(\bar{x}_i,v_i),(v_i,u_{i+1})}% {Q_i=\exists,1\le i\le n} \\ & \setunion & \bigsetof{ \ifx\customstretchb\undeftex\else% \renewcommand{\arraystretch}{\customstretchb}% \fi \begin{array}{ll} (u_i,w_i),(u_i,\bar{w}_i),(w_i,x_i),(\bar{w}_i,\bar{x}_i) \\ (x_i,v_i),(\bar{x}_i,v_i),(v_i,z_i),(z_i,u_{i+1}) \end{array} }% {Q_i=\forall,1\le i\le n} \end{array} \] \sentence % \apar{Proof of Theorem 7-6} Thus, the variable-setting component consists of \(n\) diamond-shaped gadgets that are strung together\@. The construction ensures that for each \(i\), the choice of whether to follow the path through \(x_i\) or \(\bar{x_i}\) is made by player \(0\) if \(x_i\) is a universally quantified variable, and by player \(1\) if \(x_i\) is an existentially quantified variable\@. Informally, this choice determines a truth assignment to the variable \(x_i\)\@. % \apar{Proof of Theorem 7-7} We next describe the clause-testing component\@. The node set is: \[ V_2=\setof{y_k,y_k',y_k''}{1\le k\le m}\setunion \setof{y_{kj}}{1\le k\le m,1\le j\le n^2-3} \] \sentence The edge set is \[ \begin{array}{rcl} E_2 & = & \setof{(u_{n+1},y_k)}{1\le k\le m} \\ & \setunion & \setof{(y_k,y_k'),(y_k,y_k''),(y_k',y_{k1})}{1\le k\le m} \\ & \setunion & \setof{(y_{kj},y_{kj+1})}{1\le k\le m,1\le j\le n^2-4} \\ & \setunion & \setof{(y_{kn^2-3},u_{n+1})}{1\le k\le m} \end{array} \] \sentence % \apar{Proof of Theorem 7-8} Note that, because we are assuming that the last quantifier is \(\forall\), player \(1\) chooses, from \(u_{n+1}\), an edge to some \(y_k\)\@. Informally, node \(y_k\) corresponds to a clause \(C_k\), which player \(1\) claims is true\@. At that point, player \(0\) can either move to \(y_k''\), in which case player \(0\) is challenging player \(1\) that clause \(C_k\) is false, or \(y_k'\), in which case player \(0\) is not challenging\@. If player \(0\) does not challenge, a path of length \(n^2\) is followed, back to \(u_{n+1}\), where this is repeated\@. % \apar{Proof of Theorem 7-9} Other interconnections between the clause-testing and variable-setting components are as follows: \[ \begin{array}{rcl} E_{12} & = & \setof{(y_k'',x_i)}{x_i\mbox{ occurs unnegated in clause }k} \\ & \setunion & \setof{(y_k'',\bar{x}_i)}{x_i\mbox{ occurs negated in clause }k} \end{array} \] \sentence % \apar{Proof of Theorem 7-10} Thus, if player \(0\) challenges clause \(C_k\), player \(1\) chooses a literal of the clause\@. If the literal is false, player \(0\) can follow an edge of the diamond and force player \(1\) to lose in one more move\@. % \apar{Proof of Theorem 7-11} We finally describe the line\@. The node set is \(V_3=\setof{l_i}{1\le i\le n^4}\)\@. The edge set is \(E_3=\setof{(l_j,l_{j+1})}{1\le j\le n^4-1}\)\@. Thus, this is simply a line with \(n^4-1\) edges\@. % \apar{Proof of Theorem 7-12} The following edges connect each literal node of the variable-testing component to the line: \[E_{13}=\setof{(x_i,l_1),(\bar{x}_i,l_1)}{1\le i\le n}\] \sentence The purpose of this line is to ensure that player \(0\) never challenges player \(1\) on a clause that is actually true\@. Otherwise, player \(1\) can force the game to end up on the line and thus take \(n^4\) steps, and also player \(0\) loses\@. % \apar{Proof of Theorem 7-13} Thus, the whole reduction gives \(G=(V,E)\) where \(V=V_1\setunion V_2\setunion V_3\) and \(E=E_1\setunion E_2\setunion E_{12}\setunion E_3\setunion E_{13}\)\@. % \apar{Proof of Theorem 7-14} This completes the reduction from \(\problemfunc{MAX-Q3SAT}\) and implies that there is a constant \(\epsilon\) such that approximating \(\problemset{MAX-GGEOG}\) within ratio \(\epsilon\) is \(\complexityclass{PSPACE}\)-hard\@. By reducing from \(\problemfunc{\((\log n)\)-MAX-Q-FORMULA}\) instead of \(\problemfunc{MAX-Q3SAT}\), we improve the result to ratio \(n^\epsilon\)\@. In this new reduction, \(y_k''\) is connected to a subgraph that simulates the \(k\)th formula \(\phi_k\) in the following way\@. There is a node for each of the operators of \(\phi_k\) and possibly some auxiliary nodes\@. If \(\phi_k=\phi_k'\logicor\phi_k''\), we make sure (possibly by adding an auxiliary node) that player \(1\) makes the move from the node corresponding to the \(\logicor\) operator\@. Thus, player \(1\) chooses the subformula \(\phi_k'''\) such that \(\phi_k'''=1\)\@. If \(\phi_k=\phi_k'\logicand\phi_k''\) we make sure (possibly by adding an auxiliary node) that player \(0\) makes the move from the node corresponding to the \(\logicand\) operator\@. If \(\phi_k\) is a literal, we connect it to the diamonds, as before\@. The paths from the nodes \(y_k'\) to \(u_{n+1}\) are longer than before and depend on~\(\epsilon\)\@. % {\nopagebreakbeginpar\markendlst{Proof of Theorem 7}} \end{alabsubtext} % \asection{5}{Subsequent Related Work} % \apar{5-1} This section contains a brief discussion of related work that has been done since our results first appeared \cite{cj95-04-7,cj95-04-8}\@. % \apar{5-2} A polynomial-round Arthur-Merlin game with a polynomial-time verifier~\cite{cj95-04-4} can be thought of as a \(\systemmodel{PCDS}\) in which \(r(n)\) and \(q(n)\) are both arbitrary polynomials and one of the debaters simply makes random moves\@. Let \(\complexityclass{AM}(\polyof(n))\) denote the class of languages accepted by such Arthur-Merlin games\@. In this context, the fact that \(\complexityclass{AM}(\polyof(n))=\complexityclass{PSPACE}\) (cf.~\cite{cj95-04-17} and \cite{cj95-04-22}) means that, if \(r(n)\) and \(q(n)\) are both arbitrary polynomials, then the universal debater in a \(\systemmodel{PCDS}\) can be replaced by a random debater without loss of generality\@. In~\cite{cj95-04-9} we show that, even if \(r(n)=\log n\) and \(q(n)=1\), one can replace the universal debater by a random debater and still retain the power to recognize every language in \(\complexityclass{PSPACE}\)\@. This fact has implications for the hardness of approximating \emph{stochastic} \(\complexityclass{PSPACE}\)-hard functions, of the type studied by Papadimitriou~\cite{cj95-04-19}\@. % \apar{5-3} We have described \(\complexityclass{PSPACE}\)-hard functions that do not have \(\systemmodel{PTAS}\)s, unless some unexpected collapse occurs\@. It is not hard to define a \(\complexityclass{PSPACE}\)-hard function that \emph{does} have a \(\systemmodel{PTAS}\), but the straightforward examples are artificial\@. We were thus led to ask in \cite{cj95-04-7} and \cite{cj95-04-8} whether there is a natural \(\complexityclass{PSPACE}\)-hard function that has a \(\systemmodel{PTAS}\)\@. A positive answer to this question is provided in~\cite{cj95-04-18}\@. % \apar{5-4} Bodlaender (private communication) has extended our results by showing that MAX-Q3SAT can be approximated within some \(\epsilon>0\), and by providing a simpler proof that \(\problemset{MAX-GGEOG}\) is \(\complexityclass{PSPACE}\)-hard to approximate; his proof that approximating \(\problemfunc{MAX-GGEOG}\) is hard does not involve \(\systemmodel{PCDS}\)s\@. Hunt et al.~\cite{cj95-04-13} showed, also using direct-reduction arguments, that it is \(\complexityclass{PSPACE}\)-hard to approximate several other constrained optimization problems within certain factors\@. These problems include \(\problemfunc{MAX-Q-FORMULA}\), a generalization of \(\problemfunc{\((\log n)\)-MAX-Q-FORMULA}\), where the ``clauses'' are general formulas (with no restrictions on the number of variables per ``clause'')\@. % \apar{5-5} It is not known whether characterizations of \(\complexityclass{EXP}\) and \(\complexityclass{NEXP}\) can be found that are similar to the \(\complexityclass{PCP}\) and \(\complexityclass{PCD}\) characterizations of \(\complexityclass{NP}\) and \(\complexityclass{PSPACE}\), respectively, and that lead to interesting nonapproximability results for problems that are complete for \(\complexityclass{EXP}\) or \(\complexityclass{NEXP}\)\@. % \asection{6}{Acknowledgments} % \apar{6-1} We thank Lance Fortnow and Mario Szegedy for helpful discussions in the formative stages of this work\@. We thank Jin-yi Cai, Lenore Cowen, Uriel Feige, David Johnson, Madhu Sudan, and Mihalis Yannakakis for their comments on earlier versions\@. Finally, we thank Nick Reingold for helping us typeset Section~3\@. % \end{articletext} % \begin{articlebib} % \bibliographystyle{\the\rbibstyle} \bibliography{cj95-04} % \end{articlebib} % \end{document}