\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 9}
}
\renewcommand{\headrulewidth}{0pt}
}

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

\begin{prob}
  \begin{enumerate}
    \item Given a language~$B$ in PSPACE, word $u\in B$, a word~$v\not\in
      B$, and a language~$A\in$ PSPACE, describe a TM M running in
      polynomial space that computes a function $f\colon \Sigma^{*}\to
      \Sigma^{*}$ such that~$w\in A$ if and only if~$f(w)\in B$.  Thus, on
      input~$w$, $M$ halts with~$f(w)$ on its tape.  We write
      $A\leq_{\mathrm{PSPACE}}B$.  This problem shows that everything in PSPACE
      is reducible to any other ``nontrivial'' element of PSPACE.
    \item Does the same argument work if we replace PSPACE with P?  You are
      given a nontrivial $B\in$ P and another language in~$A\in$ P.  Can you
      compute a mapping $f$ in polynomial time and conclude that $A\leq_m B$.
    \item Why are we interested polynomial time reductions and not polynomial
      space reductions?  (Relevant facts: P $\subseteq$ PSPACE, and
      PSPACE $=$ NSPACE.)
  \end{enumerate}
\end{prob}

\begin{prob}
  Consider the following generalized geography game where the start node is
  the one with the arrow pointing in from nowhere. Does Player I have a winning
  strategy? Does Player II? Give reasons for your answers.  (To start, Player I
  is at node 1 and gets to choose the next node.)
  \begin{center}
    \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding
      box.north)}]
      \node[state, initial] (1) {$1$};
      \node[state, right of=1] (2) {$2$};
      \node[state, right of=2] (3) {$3$};
      \node[state, below of=1] (4) {$4$};
      \node[state, right of=4] (5) {$5$};
      \node[state, right of=5] (6) {$6$};
      \draw (1) edge (2);
      \draw (2) edge (3);
      \draw (2) edge (4);
      \draw (3) edge (6);
      \draw (4) edge (5);
      \draw (5) edge (2);
      \draw (5) edge (6);
    \end{tikzpicture}
  \end{center}
\end{prob}

\begin{prob}
  \begin{enumerate}
    \item Encode the formula
      \[
	\exists x_{1}\forall x_{2}\exists x_{3}[(x_{1}\vee x_{2})\wedge(x_{2}\vee
	x_{3})\wedge(\overline{x_{2}}\vee \overline{x_{3}})]
      \]
      as a game of generalized geography using the method described in our book.
      The players are Player~$\exists$ and Player~$\forall$.  Player~$\exists$
      starts at the first node and gets to decide the next node.
    \item State a winning strategy for one of the players in the geography game,
      and describe how this strategy gives the truth value of the formula.
  \end{enumerate}
\end{prob}

\begin{prob}
  \begin{enumerate}
    \item Perform the following multiplication problem of two binary numbers using
      the standard algorithm from grade school:
      \begin{center}
        \begin{tikzpicture}
          \node at (0,0) {$101101$};
          \node at (0.2,-0.5) {$1011$};
	  \node at (-0.62,-0.54) {x};
	  \draw (-0.8,-0.75)--(0.6,-0.75);
        \end{tikzpicture}
      \end{center}
      This exercise will help you think about the next part of this problem.
    \item Let
      \[
        \text{MULT} = \{a\#b\#c: \text{$a, b, c$ are binary natural numbers and
	$a \times  b = c$}\}.       
      \]
      Show that MULT~$\in$ L.  [Hints: Storing the whole table of values created
      by standard multiplication cannot be done in log space.  However, you are
      allowed to use a fixed number of pointers to the read-only tape and an
      additional $O(\log(n))$ space on the work tape (why?).  Storing the carry
      might be a worry, but what is the maximum size of the carry compared to
      the length of~$a$ and $b$?]
  \end{enumerate}
\end{prob}

\begin{prob} (bonus) The cat-and-mouse game is played by two players, ``Cat'' and ``Mouse'', on
  an arbitrary undirected graph. At a given point, each player occupies a node
  of the graph. The players take turns moving to a node adjacent to the one
  that they currently
  occupy. A special node of the graph is called ``Hole''. Cat wins if the two players
  ever occupy the same node. Mouse wins if it reaches the Hole before the preceding
  happens. The game is a draw if a situation repeats (i.e., the two players
  simultaneously occupy positions that they simultaneously occupied
  previously, and it is the same player’s turn to move). Define
  \begin{align*}
    \text{HAPPY-CAT} =\{ \langle G, c, m, h\rangle| &\text{ $G, c, m, h$ are
      respectively a graph, and positions}\\
    &\qquad\text{of the Cat, Mouse, and Hole, such that Cat }\\
    &\qquad\quad \text{has a winning strategy if Cat moves first}\}.
      \end{align*}
     Show that HAPPY-CAT is in P. (Hint: The solution is not complicated and
     doesn't depend on subtle details in the way the game is defined. Consider
     the entire game tree. It is exponentially big, but you can search it in
     polynomial time. To get a feel for the solution, start by listing several
     obvious winning positions.) 
  \end{prob}
\end{document}
