\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=3cm, % 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

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

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

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

\begin{prob}
  \begin{enumerate}
    \item Carefully explain why NP $\subseteq$ PSPACE.
    \item Suppose that $A$ is PSPACE-hard.  Explain why it follows that~$A$ is
      NP-hard.  (To say $A$ is PSPACE-hard means
      that any language in PSPACE can be reduced to~$A$ in polynomial time.  We do
      not require that~$A$, itself, is in PSPACE.  Similarly, we say~$A$ is NP-hard
      if every language in NP has a polynomial-time reduction to~$A$.)
    \item Suppose that every NP-hard language is PSPACE-hard.  Would that imply
      NP $=$ PSPACE?  Explain.
  \end{enumerate}
\end{prob}

\begin{prob}
  Let $A$ and~$B$ be languages, and say $A\leq_{\text{PSPACE}}B$ if there is
  function~$f\colon \Sigma^{*}\to \Sigma^{*}$ that is computable by a TM using
  polynomial \emph{space} and such that~$w\in A$ if and only if $f(w)\in B$.
  We call $f$ a \emph{polynomial space reduction} from~$A$ to~$B$. In
  the lecture for today, Sipser states that it would be a terrible idea to use
  $\leq_{\text{PSPACE}}$ in place of polynomial \emph{time} reductions to define PSPACE
  completeness.  To see why, let $B$ be any language in PSPACE such
  that~$B\neq\emptyset$ and~$B\neq \Sigma^{*}$.  Given any language $A$ in
  PSPACE, give a polynomial space reduction $f$ from $A$ to~$B$.
\end{prob}

\begin{prob}
  The Japanese game go-moku is played by two players, $X$ and $O$, on a
  $19\times 19$ grid. Players take turns placing stones on the intersection
  points in the grid, and the first player
  to achieve five of their stones consecutively in a row, column, or diagonal is
  the winner. Consider this game generalized to an $n\times n$ board. Let 
  \begin{align*}
    GM = \{\langle P\rangle : &\text{ $P$ is a position in generalized go-moku,}\\
			      &\qquad\quad\text{where player $X$ has a winning strategy}\}. 
    \end{align*}
    By a \emph{position}~$P$ we mean a board with stones placed on it, such as may
    occur in the middle of a play of the game, together with an indication of which
    player moves next. Show that $GM\in$ PSPACE by describing a TM with numbered
    steps that accepts $GM$.  Besides creating the TM, explain why it runs in
    polynomial space.
  \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 }\\
    &\qquad\quad\text{positions of the Cat, Mouse, and Hole, such that }\\
    &\qquad\quad \text{Cat 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.) 
  \end{prob}
\end{document}
