\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*)}}
%\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, Wednesday Week 6}
}
\renewcommand{\headrulewidth}{0pt}
}

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

\begin{prob}
  Review questions.
  \begin{enumerate}
    \item What does it mean to say that a TM runs in time $t\colon \N\to \N$?
    \item What is the time complexity class $\mathrm{TIME}(t(n))$?
    \item What does it mean for two models of TMs (single-tape, multitape, etc)
      to be polynomially related?
    \item Give a precise definition of the class $P$.
  \end{enumerate}
\end{prob}

\begin{prob}
  \begin{enumerate}
    \item Prove that $n^2+n=O(n^{2})$.
    \item Prove that $O(n)+O(n\log(n))=O(n\log(n))$.  (Note: to say
      $f(n)=O(n)+O(n\log(n))$ means that there exist constants~$c,c'$ and an
      integer~$n_{0}$ such that~$n\geq n_{0}$ implies $f(n)\leq
      cn+c'n\log(n)$.  There are two directions to prove.)
    \item For which integers $m\geq0$ is $m!\geq 2^{m}$?  Give a proof.
  \end{enumerate}
\end{prob}

\begin{prob}
  True or False.  No proof required.

  \begin{tabular}{p{0.3\textwidth}p{0.3\textwidth}p{0.3\textwidth}}
    (a)\ $2n=O(n)$&(b)\ $n^2=O(n)$ &(c)\ $n^2=O(n\,\log^{2}(n))$\\
    (d)\ $n\,\log(n)=O(n^2)$&(e)\ $3^{n}=2^{O(n)}$ &(f)\
    $2^{2^{n}}=O(2^{2^{n}})$.
  \end{tabular}
\end{prob}

\begin{prob}
  True or False.  No proof required.

  \begin{tabular}{p{0.3\textwidth}p{0.3\textwidth}p{0.3\textwidth}}
    (a)\ $n=o(2n)$&(b)\ $2n=o(n^2)$ &(c)\ $2^{n}=o(3^{n})$\\
    (d)\ $1=o(n)$&(e)\ $n=o(\log(n))$ &(f)\ $1=o(1/n)$.
  \end{tabular}
\end{prob}

\begin{prob}
  Determine, with proof, whether the complexity class~$P$ is closed with respect to
  the following operations:
  \begin{enumerate}
    \item union
    \item concatenation
    \item complement.
  \end{enumerate}
  To prove a closure property holds, outline an algorithm as in Sipser's text:
  give a list of stages and show that each step in each stage uses a
  polynomial number of steps.  (Here, as usual, \emph{polynomial number} means
  polynomial in the input size.) Number your stages, indicate the run times for
  each step, and indicate the number of iterations of any loop that appears as
  in Sipser's text using big-O notation.  Compute the total run time.
\end{prob}

\begin{prob} 
  Let~$G$ be an undirected simple graph.  (Take ``simple'' to mean no multiple
  edges, no loop edges, and a finite number of vertices.)  A \emph{triangle} of
  edges is a triple of vertices $u,v,w$ such that each pair lies on an edge.
  Define
  \[
    \mathrm{TRIANGLE} = \{\langle G\rangle: \text{$G$ is a simple graph
    containing a triangle}\}.
  \]
  Show that $\mathrm{TRIANGLE}$ is in~$P$, giving a description of a polytime
  algorithm as in Sipser's
  text.  That means describing an algorithm with numbered stages giving the run
  time for each step in a stage.  Taking into account the number of times each
  loop is iterated, show your algorithm decides in polynomial time.

  Note the input size is the length~$n$ of any reasonable encoding~$\langle
  G\rangle$ of the graph $G$.  In particular, the number of vertices of $G$ is
  $O(n)$.
\end{prob}

\begin{prob} (bonus)
  Consider the language
  \[
    \mathrm{MODEXP} = \{\langle a,b,c,m\rangle: \text{$a,b,c,m$ are positive integers
    written in binary and~$a^{b}=c\bmod m$}\}.
  \]
  Show that~$\mathrm{MODEXP}\in P$.  Note that the most obvious algorithm does
  not run in polynomial time.  Hint: first try the case where~$b$ is a power
  of~$2$.
\end{prob}
\end{document}
