\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}}


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

\DeclareMathOperator{\DSPACE}{DSPACE}
\DeclareMathOperator{\NSPACE}{NSPACE}
\DeclareMathOperator{\PSPACE}{PSPACE}
\DeclareMathOperator{\Poly}{P}


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

\begin{document}
\maketitle

\begin{exercise}
  Suppose~$T\:\NN\to\NN$ is a function with~$T(n)\geq n+1$ such that there exists a \emph{single tape}
  nondeterministic Turing machine~$M_T$ such that for every input~$x$ of length~$n$, all branches of
  computation of~$M_T$ on~$x$ take time at most~$T(n)$ (i.e., the machine~$M_T$ is~$T(n)$-time bounded) and at
  least one branch of computation of~$M_T$ takes time exactly~$T(n)$.
  
  Show that a~$k$-tape nondeterministic Turing machine running in a nondeterministic time~$T(n)$ can be
  simulated by a~$2$-tape nondeterministic Turing machine running in nondeterministic time~$O(T(n))$. Note
  that, unlike the case of deterministic time, there is no additional~$\log(T(n))$ factor. Only state
  essential ideas (i.e., why we don't need the extra~$\log(T(n))$ factor) in plain English like an algorithm.
\end{exercise}

\begin{exercise}\label{ex:PSPACEvsP}
  Show that if~$\DSPACE(n)\subseteq \Poly$, then~$\PSPACE = \Poly$. Recall that~$\PSPACE = \bigcup_{k\geq
    1}\DSPACE(n^k)$. Hint: padding and~$\PSPACE$-completeness.
\end{exercise}

\begin{exercise}
  Show that~$\DSPACE(n)\neq\Poly$. Hint: reinspect Exercise~\ref{ex:PSPACEvsP} under the light of hierarchy
  theorems.
\end{exercise}

\begin{exercise}
  Show that~$\NSPACE(n)\neq\Poly$.
\end{exercise}

\end{document}
