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

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

\begin{prob}
  Review questions.
  \begin{enumerate}
    \item What is a Hamiltonian path from vertex~$s$ to vertex~$t$?
    \item What is a NTM decider? (Does it need to halt on all branches?)
    \item What does it mean to say a NTM runs in time~$O(t(n))$?  (Do all
      branches need to end in~$O(t(n))$ steps?  Only some of them?  The sum of
      the times of all branches?)
    \item Let~$t\colon \N\to \N$. What is $NTIME(t(n))$?  (Is it a set of NTMs?
      A language?)
    \item What is the class $NP$?  (Again: what, precisely, are the elements
      of~$NP$?)
  \end{enumerate}
\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}
  An undirected simple graph~$G$ is \emph{$3$-colorable} if each of its vertices
  can be assigned one of three colors in such a way no two adjacent vertices
  have the same color. (Adjacent vertices are vertices that share an edge.)
  Define the language
  \[
    \text{3COLOR} = \{\langle G\rangle: \text{$G$ is 3-colorable}\}.
  \]
  \begin{enumerate}
    \item Give some examples of graphs that are $3$-colorable and some that are
      not.
    \item How many ways are there to color a graph with~$m$ nodes using~$3$
      colors if there is no restriction on the colors of adjacent vertices?
    \item Show that 3COLOR is in NP by giving a numbered algorithm in the style
      of those given in Sipser's text.  Give the run time for each stage and the
      total run time in big-O notation.
  \end{enumerate}
\end{prob}

\begin{prob} Let~$n, b$ be integers with $n\geq1$ and~$b\geq2$.
  \begin{enumerate}
    \item Show that the number of digits of~$n$ base~$b$ is $\lfloor
      \log_{b}(n)\rfloor+1$.  Why isn't it the number of digits $\lceil
      \log_{b}(n)\rceil$?  (Hint: $n$ has $r$ digits base~$b$ if and only if~$n$
      is between which two powers of~$b$? Be careful with the endpoints of that
      interval.)
    \item  Let $a\geq2$.  Give the proof of the fact that~$f(n)=O(\log_{a}(n))$ iff
      $f(n)=O(\log_{b}(n))$.  (Thus, the number of digits of $n$ in base $b$
      is~$O(\log(n))$ no matter which base we choose.)
    \item Let~$u(n)$ be the length of~$n$ written in unary: $n =
      \overbrace{1\cdots1}^{n-\text{times}}.$ Show that~$u(n)\neq
      O(\log(n))$. 
    \item Consider the operation $d\colon \N\to \N$ defined by $d(n)=\lfloor
      n/2\rfloor$. Next, define $h\colon \N\to \N$ by $h(n)=\min\{k:
      d^{(k)}(n)=0\}$. Here, $d^{(k)}$ denotes $k$-fold composition.
      Is~$h(n)=O(\log(n))$?  Prove or disprove.
  \end{enumerate}
\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}
