\documentclass[11pt]{amsart}

\usepackage{amsmath,amsthm,amssymb}
\usepackage{stmaryrd}

\usepackage{fancyhdr} % Allows customization of verbatim environments

\usepackage{xcolor}

%\usepackage[textheight=8.5in, margin=1.6in]{geometry}
\usepackage[
  hmarginratio={1:1},     % equal left and right margins
%  vmarginratio={1:1},     % equal top and bottom margins
  %textwidth=400pt,        % new text width
  heightrounded,          % always useful
  %bindingcorrection=5mm,  % binding correction
  total={6in,8in}
]{geometry}
\headheight=13pt
\footskip=13pt

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage{graphicx}

% Tikz stuff.
\usepackage{tikz}
%\usepackage{tkz-graph}
\usepackage{pgfplots}
%\usepackage{tikz-3dplot}
\pgfplotsset{compat=newest}
%\usepgfplotslibrary{fillbetween}
%\usetikzlibrary{cd}
%\usetikzlibrary{positioning}
%\usetikzlibrary{decorations.pathmorphing}    
%\usetikzlibrary{decorations.pathreplacing}
%\usetikzlibrary{arrows.meta,calc}
%\usetikzlibrary{bending}
%\usetikzlibrary{decorations.markings,shapes.geometric}
%\tikzset{->-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{>}}},postaction={decorate}}}
%\tikzset{-|-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{stealth}}},postaction={decorate}}}
%\tikzset{movearrow/.style 2 args ={
%        decoration={markings,
%	  mark= at position {#1} with {\arrow{#2}} ,
%        },
%        postaction={decorate}
%    }
%}
%\tikzset{<--/.style={decoration={markings, mark=at position #1 with
%  {\arrow{<}}},postaction={decorate}}}
\tikzstyle{ball} = [circle,shading=ball, ball color=black,
    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{bball} = [circle,shading=ball, ball color=blue,
%    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{miniball} = [circle,shading=ball, ball color=black,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{redminiball} = [circle,shading=ball, ball color=red,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{mminiball} = [circle,shading=ball, ball color=black,
%    minimum size=0.6mm,inner sep=0.1pt]
%\tikzstyle{mycircle} = [draw,circle, minimum size=1mm,inner sep=1.3pt]
%\newcommand*{\DashedArrow}[1][]{\mathbin{\tikz [baseline=-0.25ex,-latex, dashed,#1] \draw [#1] (0pt,0.5ex) -- (1.3em,0.5ex);}}%

%%%% tikz style for finite automata
\usetikzlibrary{automata, positioning, arrows}
\tikzset{fa/.style={
    ->, % makes the edges directed
    >=stealth, % makes the arrow heads bold
    node distance=2cm, % specifies the minimum distance between two nodes. Change if necessary.
    every state/.style={thick, fill=gray!10}, % sets the properties for each ’state’ node
    initial text=$ $, % sets the text that appears on the start arrow
}}
%%%%

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage[shortlabels]{enumitem}
\setlist[enumerate]{itemsep=4pt,leftmargin=*,label={(\alph*)},topsep=4pt}
%\setlist[enumerate]{itemsep=2pt,label={\arabic*.}}

\usepackage[T1]{fontenc}
\renewcommand{\labelitemi}{\guillemotright}

\allowdisplaybreaks

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\KK}{\Bbbk}
\newcommand{\ve}{\varepsilon}
\newcommand{\scribe}{
  \begin{center}%
    Scribe~$=$ \rule{7cm}{0.15mm}%
  \end{center}%
  \medskip%
}
\DeclareMathOperator{\im}{\mathrm{im}}
\DeclareMathOperator{\id}{\mathrm{id}}
\DeclareMathOperator{\glb}{\mathrm{glb}}
\DeclareMathOperator{\lub}{\mathrm{lub}}

\newcounter{problem}
\renewcommand \thesection {\theproblem}
\newenvironment{prob}[1][]
{
\refstepcounter{problem}\par\medskip
\def\myArg{#1}
  \ifx\myArg\empty
    \noindent \textsc{Problem~\theproblem.} \rmfamily
  \else
    \noindent \textsc{Problem~\theproblem\ (\textnormal{#1}).} \rmfamily
  \fi
}
{
\medskip

}

\newenvironment{sol}
{\emph{Solution.}
}
{
  \medskip

}

\parskip = 0.05in
\parindent = 0.0in
\raggedbottom

%\pagestyle{empty}
%\pagenumbering{gobble}

\fancypagestyle{firststyle}
{
\fancyhead[L,LO]{
\textit{\small Math 387 Group problems, Wednesday Week 11}
}
\renewcommand{\headrulewidth}{0pt}
}

\begin{document}
\thispagestyle{firststyle}
\bigskip

\begin{prob} Review.
\begin{enumerate}
  \item What is a probabilistic TM?  What is the probability of a branch in a
    probabilistic TM?  What is the probability that a word is accepted?
  \item Let $M$ be a PTM.  What does it mean to say that $M$ decides a
    language~$A$ with error probability~$\varepsilon$ (where $0\leq
    \varepsilon<\frac{1}{2}$)?
  \item What is the class BPP?
\end{enumerate}  
\end{prob}

\begin{prob}
  \begin{enumerate}
    \item  Create a BP that computes the Boolean function given by the table
      \[
	\begin{array}{l|l}
	  n & f(n) \\\hline
	  00& 1  \\
	  10& 1 \\
	  01& 0  \\
	  11& 0.
	\end{array}
      \]
    \item Consider the arithmetized version of the BP you created in the
      previous part of this problem.  Let the label~$a$ of the starting node
      be~$1$, as in Sipser's lecture.  Considering the Boolean variables $x_{1}$
      and~$x_{2}$ as indeterminates, what is the output polynomial of your BP?
      (Check that it gives the right values when the variables are assigned bit values.)
    \item Construct AND and OR gates using BPs.
    \item Consider the arithmetized version of your AND BP letting the Boolean
      variables be indeterminates.  What is the output polynomial?  (Check your
      solution has the right values when the variables are assigned bit values.)
  \end{enumerate}
\end{prob}

\begin{prob}
  Show that BPP $\subseteq$ PSPACE.
\end{prob}

\begin{prob}\ 
  [NOTE: This problem is too easy.  Next time randomize the values of~$f$.] Create a BP that computes the boolean function given by the table
  \[
    \begin{array}{l|l}
      n & f(n) \\\hline
      000& 1  \\
      001& 1 \\
      010& 1  \\
      011& 1  \\
      100& 0  \\
      101& 0  \\
      110& 0  \\
      111& 0  \\
    \end{array}
  \]
\end{prob}

\begin{prob} (bonus) 
  Describe how to construct a BP that computes any given Boolean function
  $f\colon \{0,1\}^{m}\to \{0,1\}$.
\end{prob}

\begin{prob} (bonus)
  If EQ$BP\in$ BPP, show that NP $\subseteq$ BPP.
\end{prob}

\begin{prob} (bonus)
  Show that~$EQBP$ is coNP-complete: 
  \begin{enumerate}
    \item Why is $EQBP$ in coNP?
    \item Given any language $A$ in coNP, give a polynomial time mapping to EQBP.
  \end{enumerate}
\end{prob}
\end{document}
