% 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 \(j<t\)\@. The debate format is thus
\((f(n),g(n))\), where \(g(n)\) is chosen to make the error
probability small enough and \(f(n)\) is chosen to allow encoding of
binary trees of the appropriate form; we will explain in detail how to
choose \(f\) and \(g\) when we prove correctness of the protocol\@.
%
\apar{Proof of Theorem 3-6}
Before specifying the algorithm of the verifier \(V\), we give some
examples of debates in which player \(1\) is honest\@. The values assigned
to the variables depend on the input formula and are unimportant for
the purposes of this discussion\@.
%
\begin{figure*}
%
\begin{center}
\setlength{\unitlength}{0.04em}
\begin{picture}(345,1085)(0,-10)
%
\put(340,925){\circle*{10}}
\put(340,925){\circle*{10}}
\put(240,905){\makebox(0,0)[lb]{{\small\(x_1=T\)}}}
\put(240,1005){\circle*{10}}
\put(240,1005){\circle*{10}}
\put(300,1065){\circle*{10}}
\put(300,1065){\circle*{10}}
\put(240,1005){\line(1,1){60} }
\put(240,1005){\line(1,1){60} }
\put(200,1045){\makebox(0,0)[lb]{{\small\(x_1=T\)}}}
\put(218,537){\circle*{6}}
\put(218,537){\circle*{6}}
\put(218,517){\circle*{6}}
\put(218,517){\circle*{6}}
\put(218,497){\circle*{6}}
\put(218,497){\circle*{6}}
\put(218,262){\circle*{6}}
\put(218,262){\circle*{6}}
\put(218,242){\circle*{6}}
\put(218,242){\circle*{6}}
\put(218,222){\circle*{6}}
\put(218,222){\circle*{6}}
\put(220,340){\circle*{10}}
\put(220,340){\circle*{10}}
\put(280,400){\circle*{10}}
\put(280,400){\circle*{10}}
\put(220,140){\circle*{10}}
\put(220,140){\circle*{10}}
\put(280,200){\circle*{10}}
\put(280,200){\circle*{10}}
\put(218,77){\circle*{6}}
\put(218,77){\circle*{6}}
\put(218,57){\circle*{6}}
\put(218,57){\circle*{6}}
\put(218,37){\circle*{6}}
\put(218,37){\circle*{6}}
\put(220,805){\circle*{10}}
\put(220,805){\circle*{10}}
\put(280,555){\circle*{10}}
\put(280,555){\circle*{10}}
\put(220,615){\circle*{10}}
\put(220,615){\circle*{10}}
\put(280,675){\circle*{10}}
\put(280,675){\circle*{10}}
\put(280,865){\circle*{10}}
\put(280,865){\circle*{10}}
\put(340,735){\circle*{10}}
\put(340,735){\circle*{10}}
\put(170,170){\makebox(0,0)[lb]{{\small\(x_n = T\)}}}
\put(280,280){\circle*{10}}
\put(280,280){\circle*{10}}
\put(340,460){\circle*{10}}
\put(340,460){\circle*{10}}
\put(220,805){\line(1,1){60} }
\put(280,865){\line(1,1){60} }
\put(220,615){\line(1,-1){60} }
\put(220,615){\line(1,-1){60} }
\put(220,615){\line(1,1){60} }
\put(280,675){\line(1,1){60} }
\put(220,340){\line(1,-1){60} }
\put(220,340){\line(1,-1){60} }
\put(220,340){\line(1,1){60} }
\put(280,400){\line(1,1){60} }
\put(220,140){\line(1,1){60} }
\put(220,140){\line(1,1){60} }
\put(65,1060){\makebox(0,0)[lb]{{\small Round 1:}}}
\put(60,920){\makebox(0,0)[lb]{{\small Round 2:}}}
\put(60,730){\makebox(0,0)[lb]{{\small Round 3:}}}
\put(265,585){\makebox(0,0)[lb]{{\small\(x_3=F\)}}}
\put(240,715){\makebox(0,0)[lb]{{\small\(x_1=T\)}}}
\put(175,645){\makebox(0,0)[lb]{{\small\(x_2=T\)}}}
\put(175,835){\makebox(0,0)[lb]{{\small\(x_2=T\)}}}
\put(265,310){\makebox(0,0)[lb]{{\small\(x_3=F\)}}}
\put(240,440){\makebox(0,0)[lb]{{\small\(x_1=T\)}}}
\put(190,105){\makebox(0,0)[lb]{{\small Same as round \(n\).}}}
\put(190,0){\makebox(0,0)[lb]{{\small Same as round \(n\).}}}
\put(45,455){\makebox(0,0)[lb]{{\small Round \(n\):}}}
\put(45,0){\makebox(0,0)[lb]{{\small Round \(g\):}}}
\put(0,105){\makebox(0,0)[lb]{{\small Round \(n+1\):}}}
\put(175,370){\makebox(0,0)[lb]{{\small\(x_2=T\)}}}
%
\end{picture}
\end{center}
%
\afigcap{2}{Both player \protect\(1\protect\) and player
  \protect\(0\protect\) are honest\@.}
%
\end{figure*}
%
\begin{alabsubtext}{Example}{1}{}
\exampfontshape
%
Suppose that player \(0\) is honest as well (see Figure~2)\@. In round
\(t\), \(1\leq t\leq n\), player \(i\equiv t\bmod 2\) assigns a value
to \(x_t\) by writing down a path of length \(t\) that extends the
path written in round \(t-1\)\@. The path written in round \(n\) is
\(P\), the intersection of \(A_1\) and \(A_0\)\@. In rounds \(n+1\)
through \(g\), the path \(P\) is repeated in each round\@. Verifier \(V\) will
declare player \(1\) the winner (i.e., accept the input) if and only
if \(P\) satisfies~\(\phi\)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Example}{2}{}
\exampfontshape
%
Suppose that \(\Phi\in\problemset{QBF}\) and that player
\(0\) cheats in an effort to convince \(V\) to reject (see
Figure~3)\@. One way player \(0\) may do this is to play a move that is
not a subtree of \(A_1\)---that is, to lie about player \(1\)'s
previous moves\@.
%
\end{alabsubtext}
%
\begin{figure*}
%
\begin{center}
\setlength{\unitlength}{0.04em}
\begin{picture}(430,541)(0,-10)
%
\put(283,23){\circle*{6}}
\put(283,23){\circle*{6}}
\put(283,3){\circle*{6}}
\put(283,3){\circle*{6}}
\put(280,521){\circle*{10}}
\put(280,521){\circle*{10}}
\put(340,461){\circle*{10}}
\put(340,461){\circle*{10}}
\put(280,421){\circle*{10}}
\put(280,421){\circle*{10}}
\put(340,361){\circle*{10}}
\put(340,361){\circle*{10}}
\put(400,301){\circle*{10}}
\put(400,301){\circle*{10}}
\put(220,361){\circle*{10}}
\put(220,361){\circle*{10}}
\put(160,301){\circle*{10}}
\put(160,301){\circle*{10}}
\put(280,261){\circle*{10}}
\put(280,261){\circle*{10}}
\put(340,201){\circle*{10}}
\put(340,201){\circle*{10}}
\put(400,141){\circle*{10}}
\put(400,141){\circle*{10}}
\put(340,81){\circle*{10}}
\put(340,81){\circle*{10}}
\put(280,521){\line(1,-1){60} }
\put(280,521){\line(1,-1){60} }
\put(280,421){\line(1,-1){60} }
\put(280,421){\line(1,-1){60} }
\put(283,43){\circle*{6}}
\put(283,43){\circle*{6}}
\put(340,361){\line(1,-1){60} }
\put(340,361){\line(1,-1){60} }
\put(0,256){\makebox(0,0)[lb]{{\small Round 3:}}}
\put(160,301){\line(1,1){60} }
\put(160,301){\line(1,1){60} }
\put(220,361){\line(1,1){60} }
\put(220,361){\line(1,1){60} }
\put(280,261){\line(1,-1){60} }
\put(280,261){\line(1,-1){60} }
\put(340,201){\line(1,-1){60} }
\put(340,201){\line(1,-1){60} }
\put(340,81){\line(1,1){60} }
\put(340,81){\line(1,1){60} }
\put(320,486){\makebox(0,0)[lb]{{\small\(x_1=F\)}}}
\put(315,396){\makebox(0,0)[lb]{{\small\(x_1=F\)}}}
\put(370,336){\makebox(0,0)[lb]{{\small\(x_2=F\)}}}
\put(180,391){\makebox(0,0)[lb]{{\small\(x_1=T\)}}}
\put(130,336){\makebox(0,0)[lb]{{\small\(x_2=T\)}}}
\put(310,241){\makebox(0,0)[lb]{{\small\(x_1=F\)}}}
\put(370,176){\makebox(0,0)[lb]{{\small\(x_2=F\)}}}
\put(295,116){\makebox(0,0)[lb]{{\small\(x_3=T\)}}}
\put(0,511){\makebox(0,0)[lb]{{\small Round 1:}}}
\put(0,411){\makebox(0,0)[lb]{{\small Round 2:}}}
%
\end{picture}
\end{center}
%
\afigcap{3}{Player \protect\(1\protect\) is honest and player
  \protect\(0\protect\) is lying about player \protect\(1\protect\)'s moves\@.}
%
\end{figure*}
%
Note that, in round \(3\), the honest player \(1\) need only extend
the \(FF\) path of the tree played by \(0\) in round \(2\)\@. Because the
\(TT\) path that appears in round \(2\) is not in \(A_1\), i.e., because
it is not consistent with player \(1\)'s move in round \(1\), it does
not satisfy the definition of a challenge\@.
%
\begin{alabsubtext}{Example}{3}{}
\exampfontshape
%
Once again, suppose that \(\Phi\) is true and that player \(0\)
cheats\@. This time, player \(0\) does so by lying about player \(0\)'s
own moves, rather than those of player \(1\) (see Figure~4)\@.
%
\end{alabsubtext}
%
\begin{figure*}
%
\begin{center}
\setlength{\unitlength}{0.04em}
\begin{picture}(417,921)(0,-10)
\put(198,23){\circle*{6}}
\put(198,23){\circle*{6}}
\put(198,3){\circle*{6}}
\put(198,3){\circle*{6}}
\put(200,901){\circle*{10}}
\put(200,901){\circle*{10}}
\put(260,841){\circle*{10}}
\put(260,841){\circle*{10}}
\put(200,801){\circle*{10}}
\put(200,801){\circle*{10}}
\put(260,741){\circle*{10}}
\put(260,741){\circle*{10}}
\put(200,681){\circle*{10}}
\put(200,681){\circle*{10}}
\put(200,641){\circle*{10}}
\put(200,641){\circle*{10}}
\put(260,581){\circle*{10}}
\put(260,581){\circle*{10}}
\put(200,521){\circle*{10}}
\put(200,521){\circle*{10}}
\put(140,461){\circle*{10}}
\put(140,461){\circle*{10}}
\put(200,421){\circle*{10}}
\put(200,421){\circle*{10}}
\put(260,361){\circle*{10}}
\put(260,361){\circle*{10}}
\put(320,301){\circle*{10}}
\put(320,301){\circle*{10}}
\put(200,261){\circle*{10}}
\put(200,261){\circle*{10}}
\put(260,201){\circle*{10}}
\put(260,201){\circle*{10}}
\put(320,141){\circle*{10}}
\put(320,141){\circle*{10}}
\put(380,81){\circle*{10}}
\put(380,81){\circle*{10}}
\put(200,141){\circle*{10}}
\put(200,141){\circle*{10}}
\put(140,81){\circle*{10}}
\put(140,81){\circle*{10}}
\put(200,901){\line(1,-1){60} }
\put(200,901){\line(1,-1){60} }
\put(200,801){\line(1,-1){60} }
\put(200,801){\line(1,-1){60} }
\put(200,681){\line(1,1){60} }
\put(200,681){\line(1,1){60} }
\put(198,43){\circle*{6}}
\put(198,43){\circle*{6}}
\put(200,641){\line(1,-1){60} }
\put(200,641){\line(1,-1){60} }
\put(90,111){\makebox(0,0)[lb]{{\small\(x_3=T\)}}}
\put(200,521){\line(1,1){60} }
\put(200,521){\line(1,1){60} }
\put(140,461){\line(1,1){60} }
\put(140,461){\line(1,1){60} }
\put(200,421){\line(1,-1){60} }
\put(260,361){\line(1,-1){60} }
\put(320,141){\line(1,-1){60} }
\put(260,201){\line(1,-1){60} }
\put(200,261){\line(1,-1){60} }
\put(195,136){\line(1,1){65} }
\put(195,136){\line(1,1){65} }
\put(140,81){\line(1,1){60} }
\put(140,81){\line(1,1){60} }
\put(245,866){\makebox(0,0)[lb]{{\small\(x_1=F\)}}}
\put(0,896){\makebox(0,0)[lb]{{\small Round 1:}}}
\put(0,791){\makebox(0,0)[lb]{{\small Round 2:}}}
\put(240,771){\makebox(0,0)[lb]{{\small\(x_1=F\)}}}
\put(165,711){\makebox(0,0)[lb]{{\small\(x_2=T\)}}}
\put(0,631){\makebox(0,0)[lb]{{\small Round 3:}}}
\put(240,611){\makebox(0,0)[lb]{{\small\(x_1=F\)}}}
\put(105,496){\makebox(0,0)[lb]{{\small\(x_3=T\)}}}
\put(0,411){\makebox(0,0)[lb]{{\small Round 4:}}}
\put(240,386){\makebox(0,0)[lb]{{\small\(x_1=F\)}}}
\put(300,331){\makebox(0,0)[lb]{{\small\(x_2=F\)}}}
\put(240,226){\makebox(0,0)[lb]{{\small\(x_1=F\)}}}
\put(300,166){\makebox(0,0)[lb]{{\small\(x_2=F\)}}}
\put(360,106){\makebox(0,0)[lb]{{\small\(x_3=F\)}}}
\put(165,171){\makebox(0,0)[lb]{{\small\(x_2=T\)}}}
\put(0,251){\makebox(0,0)[lb]{{\small Round 5:}}}
\put(155,551){\makebox(0,0)[lb]{{\small\(x_2=T\)}}}
%
\end{picture}
\end{center}
%
\afigcap{4}{Player \protect\(1\protect\) is honest and player
  \protect\(0\protect\) is lying about player \protect\(0\protect\)'s
  own moves\@.}
%
\end{figure*}
%
In this example, both the \(FF\) path of round \(4\) and the \(FT\) path of
round \(2\) require a response by player \(1\) in round \(5\), because
both are legitimate challenges, i.e., neither is inconsistent with
player \(1\)'s previous moves\@.
%
\apar{Proof of Theorem 3-7}
A move \(T_t\) by an honest player \(i\) must have the following
properties: (i)~at most one edge from every node is an \(i\)-edge
(because \(T_t\) is a subtree of \(A_i\)); and (ii)~the edge to every
leaf of depth \(< n+1\) is an \(i\)-edge (because player \(i\)
responds to each recorded challenge by player \(1-i\))\@. A tree \(T_t\)
satisfying these two properties is \emph{valid}\@. (In Example~3 above,
player \(0\) should choose which of the paths \(FTT\) or \(FFF\) of round
\(5\) to extend in round 6, because extending both of them would
result in an invalid move \(T_6\)\@.) Also, we define a \emph{valid
challenge} by player \(1-i\) to player \(i\) at round \(j\) to be
the (unique) longest challenge that lies in \(T_j\), if \(T_j\) is
valid\@.
%
\apar{Proof of Theorem 3-8}
Note that if player \(i\) is honest, then \(T_{t-2}\) is a subtree of
\(T_t\)\@. This is because both \(T_{t-2}\) and \(T_t\) respond to all
valid challenges from rounds \(j<t-2\)\@. Also, \(T_t\) has at most one
more leaf than \(T_{t-2}\), namely, the leaf of the path that contains
the valid challenge at round \(t-1\), if it lies on a different path
from previous valid challenges\@.
%
\apar{Proof of Theorem 3-9}
We take the number of rounds to be \(g=g(n)>4n\); 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<g-1\) is even\@. The move \(T_t\) contains a
(unique) longest prefix of \(P(g)\), say \(P(t)\)\@. Informally, we
say that player \(0\) ``cooperates'' if
\(\setsize{P(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\), \(1<t<g\), in which player \(1\)
plays, and examines rounds \(t\) and \(t-1\)\@. If \(T_t\) is not valid
or is not a subtree of \(T_g\), \(V\) rejects\@. Similarly, if
\(T_{t-1}\) is not valid or is not a subtree of \(T_{g-1}\), \(V\)
accepts\@. Otherwise, let \(P'\) be the longest path in both \(T_{t-1}\)
and \(T_t\)\@. If the last edge of \(P'\) is not a \(0\)-edge, then
\(V\) rejects\@. Otherwise, \(V\) accepts\@. This completes the statement
of \(V\)'s algorithm\@.
%
\apar{Proof of Theorem 3-13}
Now, suppose that \(\Phi\in\problemset{QBF}\) and that player \(1\) is
honest\@. We show that \(V\) accepts with probability \(1\)\@. This is
true if the length of \(P(g)\) is \(n\), since in this case \(P(g)\)
is a path in \(A_1\) and hence satisfies \(\phi\)\@. If the length of
\(P(g)\) is less than \(n\), then for all rounds \(t\) in which player
\(1\) plays, \(T_t\) is valid and a subtree of \(T_g\)\@. Suppose that
\(T_{t-1}\) is also valid and a subtree of \(T_{g-1}\)\@. It remains to
show that the longest path \(P'\) in both \(T_{t-1}\) and \(T_t\) must
end in a \(0\)-edge\@.
%
\apar{Proof of Theorem 3-14}
First, note that the length of \(P'\) must be \(<n\); otherwise \(P'\)
is contained in both \(T_{g-1}\) and \(T_g\) and therefore
\(P'=P(g)\), which contradicts our assumption that the length of
\(P(g)\) is \(<n\)\@. Also, since \(T_{t-1}\) is valid, all paths of
\(T_{t-1}\) of length \(< n\) that end in a \(1\)-edge are followed by
a \(0\)-edge\@. Furthermore, if \(P'\) ends in a \(1\)-edge, the
\(0\)-edge following \(P'\) in \(T_{t-1}\) must also be in \(T_t\),
since the path formed by \(P'\) and this \(0\)-edge is a prefix of the
valid challenge of player \(0\) to player \(1\) at round \(t-1\), and
player \(1\) is honest\@. This contradicts the fact that \(P'\) is the
longest path in both \(T_{t-1}\) and \(T_t\)\@. Hence \(P'\) must end in
a \(0\)-edge\@.
%
\apar{Proof of Theorem 3-15}
We next show that if \(\Phi\notin\problemset{QBF}\) and player \(0\)
is honest, then \(V\) accepts with probability at most
\(2(n-1)/(g-3)\)\@. If the length of \(P(g)\) is \(n\), \(V\) rejects,
since in this case \(P(g)\) is a path in \(A_0\), and therefore does
not satisfy \(\phi\)\@. Hence suppose that the length of \(P(g)\) is
less than \(n\); thus player \(1\) cannot be honest\@. We claim that in
this case, there can only be \(n-1\) values of \(t\) such that \(V\)
accepts when rounds \(t\) and \(t-1\) are examined\@. Since \(V\)
chooses \(t\) randomly and uniformly from \((g-3)/2\) choices, the
error probability is at most \(2(n-1)/(g-3)\)\@. The number of choices
for \(t\) is \((g-3)/2\), because \(V\) never chooses player \(1\)'s
first move, since it is not preceded by a move of player \(0\)\@.
%
\apar{Proof of Theorem 3-16}
If \(T_t\) is valid, let \(p(t)\) be the length of \(P(t)\), where
\(P(t)\) is the longest prefix of \(P(g)\) in \(T_t\)\@. For every
\(t\) such that player \(1\) plays in round \(t\), we show that, if
\(V\) accepts on examining rounds \(t\) and \(t-1\), then
\(p(t)>p(j)\) for all \(j<t\) such that \(T_j\) is valid\@. This implies
the claim, since then \(V\) accepts only the first round for which
\(p(i)=1,p(i)=2,\ldots,p(i)=n-1\), and there are at most \(n-1\) such
rounds\@.
%
\apar{Proof of Theorem 3-17}
Suppose, then, that \(V\) accepts on examining rounds \(t\) and
\(t-1\)\@. Suppose that \(j<t\) is a round of player \(1\), where
\(T_j\) is valid\@. We need to show \(p(j)<p(t)\)\@. We first show that
\(P(j)\) is a prefix of \(P(t-1)\), which implies that \(p(j)\le
p(t-1)\)\@. This is because \(P(j)\), with the last edge removed if it
is a \(0\)-edge, is the prefix of a valid challenge of player \(1\) to
player \(0\) at round \(j\), and since player \(0\) is honest, player
\(0\) responds to this challenge at round \(t-1\)\@. To complete the
proof, we show that \(p(t-1)<p(t)\)\@. Note that it must be the case
that \(P'\), the longest path in both \(T_{t-1}\) and \(T_t\), ends in
a \(0\)-edge, since \(V\) accepts\@. Also, this path must be a prefix of
\(P(t-1)\) and \(P(t)\)\@. In fact, this path must equal \(P(t-1)\)\@.
(Otherwise, the \(1\)-edge following \(P'\) in \(P(t-1)\) must be in
\(T_g\)\@. Since \(T_t\) is a subtree of \(T_g\), this \(1\)-edge must
be the \(1\)-edge of \(T_t\) following \(P'\), contradicting the fact
that \(P'\) is the longest path in both \(T_{t-1}\) and \(T_t\)\@.)
Finally, the \(1\)-edge following \(P'\) in \(T_t\) must be in \(T_g\)
(since \(V\) checks for this) and also in \(T_{g-1}\) (since player
\(0\) is honest)\@. Thus \(P(t)\) contains \(P(t-1)\) as a prefix, and
it also contains an additional \(1\)-edge\@. This implies that
\(p(t)>p(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}