\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\MAXSAT}{\mbox{\sc MAX3SAT}}
\newcommand{\NP}{\mbox{NP}}
\newcommand{\PCP}[3]{\mbox{PCP}_{#1}(#2,#3)}

\head{CSG714}{Theory of Computation}{Spring 2008}{16 April 2008}{22}

\begin{center}
\Large{\bf Problem of the Week -- 12}
\end{center}

In Problem Set 6, we defined $\PCP{\eps}{r(n)}{q(n)}$ as the set of
languages that have a PCP protocol using $O(r(n))$ random bits and
$O(q(n))$ queries to achieve soundness error $\eps$ (there is no error
with respect to completeness).

\begin{itemize}
\item
What is the set $\PCP{0}{\log n}{\mbox{poly}(n)}$?

\item
What is the set $\PCP{2^{-n}}{\log n}{\mbox{poly}(n)}$?

\item
What is the set $\PCP{1/2}{\log n}{\mbox{poly}(n)}$?
\end{itemize}

\end{document}