\documentclass[11pt, a4paper, notitlepage, onecolumn, oneside, openany]{article}

\input{packages}
\input{layout}
\input{common_math}
\input{theorem_names_en}

\setlist[enumerate]{label={(\alph*)}, ref={(\alph*)}}
\setlist[description]{labelindent={2em}}

\def\bP{\operatorname{\textbf{P}}}
\def\bNP{\operatorname{\textbf{NP}}}
\DeclareMathOperator{\TIME}{TIME}
\DeclareMathOperator{\REVERSAL}{REVERSAL}
\DeclareMathOperator{\pad}{pad}
\DeclareMathOperator{\Fac}{Fac}
\DeclareMathOperator{\UFac}{UnaryFac}
\DeclareMathOperator{\UHC}{UHC}
\DeclareMathOperator{\HC}{HC}

% Number algorithms under problems
\makeatletter
\renewcommand\thealgocf{%
  \theproblem.\arabic{algocf}}
\@addtoreset{algocf}{problem}
\makeatother


\title{%
  CMSC~28100-1 / MATH~28100-1\\
  Introduction to Complexity Theory\\
  Fall~2017 -- Homework~6
}
\author{\relax}
\date{\today}

\begin{document}
\maketitle

\begin{exercise}
  Let~$\bP$ be the complexity class of all languages decidable in polynomial time, that is, we have~$\bP =
  \bigcup_{k\geq 1}\TIME(n^k)$. Prove that~$\bP\neq\TIME(n^3)$. (Hint: use the Time Hierarchy Theorem.)
\end{exercise}

\begin{exercise}
  The number of \emph{head reversals} of a single-tape Turing machine~$M$ on input~$x$ is the number of times
  the tape head changes direction, that is, it was moving left and it moves right, or vice-versa. (Not moving
  does not count as reversing direction, but e.g.\ moving right, not moving then moving left does.)

  Let~$\REVERSAL(r(n))$ denote the class of languages decidable by Turing machines that on inputs of
  length~$n$ use at most~$r(n)$ head reversals.

  A function~$R\:\NN\to\NN$ is said to be \emph{fully reversal constructible} if there exists a Turing
  machine~$M_R$ that always halts and takes exactly~$R(n)$ head reversals on inputs of length~$n$.

  Prove the following head reversal hierarchy theorem: if~$\lim_{n\to\infty} r(n)^2/R(n) = 0$ and~$R$ is fully
  reversal constructible, then there exists a language in~$\REVERSAL(k R(n))$ that is not in~$\REVERSAL(r(n))$
  for some fixed~$k > 0$. You can assume the following fact: if a Turing machine~$M$ on input~$w$ requires at
  most~$r$ head reversals, then the simulation of~$M$ on~$w$ can be done by a Universal Turing Machine using
  less than~$r^2$ head reversals. (Hint: mimic the proof of the Time Hierarchy Theorem.)
\end{exercise}

\begin{exercise}[Based on Exercise~9.13 of Sipser's ``Introduction to Theory of Computation'']
  Consider the function~$\pad\:\Sigma^*\times\NN\to\Sigma^*\#^*$ that is defined as
  follows. Let~$\pad(s,\ell) = s\#^j$, where~$j = \max\{0,\ell-\lvert s\rvert\}$ and~$\lvert s\rvert$ is the
  length of~$s$. Thus~$\pad(s,\ell)$ simply adds enough copies of the new symbol~$\#$ to the end of~$s$ so
  that the length of the resulting string is at least~$\ell$. For any language~$A$ and
  function~$f\:\NN\to\NN$, define the language~$\pad(A,f(m))$ as
  \begin{align*}
    \pad(A,f(m)) & = \{\pad(s,f(\lvert s\rvert)) : s\in A\}.
  \end{align*}

  \begin{enumerate}
  \item Prove that if~$A\in\TIME(n^6)$, then~$\pad(A,n^2)\in\TIME(n^3)$.
  \item Let~$\Fac$ be the language
    \begin{align*}
      \Fac & = \{(x,y) : x,y\in\NN\text{ are written in \emph{binary} and~$x$ has a non-trivial factor}\\
        & \qquad \text{that is less or equal to~$y$}\}.
    \end{align*}
    A non-trivial factor of~$x$ is a positive divisor of~$x$ that is neither~$1$ nor~$x$. Show that~$\Fac$ can
    be decided in time~$O(x(\log x)^2) = O(2^n n^2)$, where~$n = \lvert x\rvert$ is the length of~$x$. You can
    assume the following fact: given two integers~$x$ and~$y$ in binary, one can decide whether~$y$ is a
    factor of~$x$ in~$O(n^2)$ steps, where~$n$ is the number of digits in~$x$.
  \item Let~$\UFac$ be the language
    \begin{align*}
      \UFac & = \{(x,y) : x,y\in\NN\text{ are written in \emph{unary} and~$x$ has a non-trivial factor}\\
      & \qquad \text{that is less or equal to~$y$}\}.
    \end{align*}
    Show that~$\UFac\in\TIME(n(\log n)^2)$, where~$n$ is the length of~$x$. (The \emph{unary} representation
    of an integer~$x$ is the string~$1^x$.)
  \item Show that~$\pad(\Fac,2^n)\in\TIME(n(\log n)^2)$.
  \end{enumerate}
\end{exercise}

\begin{exercise}[Undirected Hamiltonian Circuit is~$\bNP$-complete]
  Prove that the undirected Hamiltonian Circuit Problem~$\UHC$ (i.e., the Hamiltonian Circuit Problem for
  undirected graphs) is~$\bNP$-complete. You can assume that the Directed Hamiltonian Circuit Problem~$\HC$
  is~$\bNP$-complete. (Hint: do a polynomial (many-to-one) reduction to~$\HC$. Remember to state what the
  input of your reduction is, what it produces and why this implies that~$\UHC$ is~$\bNP$-complete.)
\end{exercise}

\end{document}
