\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, Monday Week 12}
}
\renewcommand{\headrulewidth}{0pt}
}

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

\begin{prob}
Give two branching programs $B_{1}$ and $B_{2}$ that agree on all Boolean input
but have different output polynomials when arithmetized.  (Try to find a simple
example.)
\end{prob} 

\begin{prob}
  \begin{enumerate}
    \item Prove that if~$A$ is a regular language, a family of branching programs
      $(B_{1},B_{2},\ldots)$ exists where each~$B_{n}$ accepts exactly the
      strings in~$A$ of length~$n$ and is bounded in size by a constant
      times~$n$.  It may help to describe your BP one level at a time.  (Take
      the size of a BP to be the number of nodes plus the number of edges.)
      \begin{enumerate}[(i)]
        \item Describe the construction of each $B_{n}$.
	\item Prove that the size of~$B_{n}$ is $O(n)$.
      \end{enumerate}
    \item Illustrate your proof by creating~$B_{3}$ for the regular language
      generated by the following~$DFA$:
      \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	\node[state, initial] (q1) {$q_1$};
	\node[state, above right of=q1] (q2) {$q_2$};
	\node[state, accepting, right of=q2] (q3) {$q_3$};
	\draw (q1) edge[above left] node{0} (q2);
	\draw (q2) edge[loop above] node{0} (q2);
	\draw (q2) edge[above, bend left] node{1} (q3);
	\draw (q3) edge[above, bend left] node{0} (q2);
	\draw (q3) edge[loop right] node{1} (q3);
	\node[state, below right of=q1] (q4) {$q_4$};
	\node[state, accepting, right of=q4] (q5) {$q_5$};
	\draw (q1) edge[below left] node{1} (q4);
	\draw (q4) edge[loop below] node{1} (q4);
	\draw (q4) edge[above, bend left] node{0} (q5);
	\draw (q5) edge[below, bend left] node{1} (q4);
	\draw (q5) edge[loop right] node{0} (q5);
    \end{tikzpicture}
  \end{enumerate}
\end{prob}

\begin{prob}  The \emph{parity function on $n$ inputs} is the Boolean function
  that returns~$1$ if the number of~$1$s in the input is odd, and returns~$0$,
  otherwise. Show that the parity function with~$n$ inputs can be computed by a
  branching program that has~$O(n)$ nodes by drawing the example when $n=4$ in a
  way that clearly generalizes to arbitrary~$n$.
\end{prob}

\begin{prob} 
  Here is Chat GPT's proof that EQBP is coNP-complete.  I asked it to give a
  reduction of the complement of SAT to EQBP.  Is the proof correct?  If not,
  can you fix it?

  \begin{proof}
   Given a Boolean formula $F$, let's construct two branching programs $P$ and
   $Q$ as follows:
   
   For each clause $C$ in $F$, create a branching program that accepts all
   assignments that satisfy~$C$. We can construct such a branching program using
   the standard technique of creating a binary decision tree with the variables
   of $C$ as internal nodes and the literals of $C$ as leaf nodes.
   
   Combine the branching programs for all clauses using a binary AND operation,
   resulting in the branching program $P$ that accepts all satisfying assignments
   of $F$.
   
   Negate each literal in the branching programs for all clauses, and then
   combine the branching programs for all clauses using a binary OR operation.
   The resulting branching program $Q$ accepts all non-satisfying assignments of
   $F$.
   
   Finally, check whether $P$ and $Q$ are equivalent using EQBP.
   
   The construction of $P$ and $Q$ takes a polynomial number of operations, as
   each clause has a polynomial number of variables, and each variable has a
   polynomial number of possible values. Thus, the total number of branching
   program nodes is polynomial in the size of the input formula. The EQBP problem
   can also be solved in polynomial time, so the entire reduction can be done in
   polynomial time.
   
   Now, if $F$ is unsatisfiable, then $P$ and $Q$ will be equivalent, as there
   are no satisfying assignments for $F$, and thus $P$ and $Q$ will both accept
   no inputs. Conversely, if $F$ is satisfiable, then $P$ and $Q$ will not be
   equivalent, as there exists at least one satisfying assignment for $F$, which
   is accepted by $P$ and not by $Q$.
   
   Therefore, we have shown a polynomial-time reduction from the complement of
   SAT to EQBP, which implies that EQBP is at least as hard as the complement of
   SAT, and hence EQBP is coNP-complete.
  \end{proof}
\end{prob}
\end{document}
