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

\DeclareMathOperator{\Poly}{P}
\DeclareMathOperator{\NP}{NP}
\DeclareMathOperator{\NTIME}{NTIME}
\DeclareMathOperator{\SAT}{SAT}

% 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~8
}
\author{\relax}
\date{\today}

\begin{document}
\maketitle

\begin{exercise}
  Show that if~$\Poly = \NP$, then every language in~$\NP$ is~$\NP$-complete, except for~$\varnothing$
  and~$\Sigma^*$.
\end{exercise}

\begin{exercise}
  Consider the following language:
  \begin{align*}
    K & = \{(M,x,1^t) : M\text{ is an NTM that accepts~$x$ within~$t$ steps}\}.
  \end{align*}

  \begin{enumerate}
  \item Show that~$K\in\NTIME(n)$.
  \item Show directly (not by reduction from another known~$\NP$-complete language) that~$K$
    is~$\NP$-complete.
  \end{enumerate}
\end{exercise}

\begin{exercise}\label{ex:search}
  Show that if~$\SAT\in\Poly$, then there is a deterministic polynomial-time Turing machine~$M$ such that for
  all formulas~$\phi$, if~$\phi$ is satisfiable then~$M(\phi)$ outputs a satisfying assignment to~$\phi$, and
  otherwise~$M$ rejects. This is called solving the ``search version'' of~$\SAT$ (searching for a witness,
  rather than merely determining if one exists).
\end{exercise}

\begin{exercise}
  A language~$L$ is~\emph{$p$-selective} if there is a polynomial-time (deterministic) Turing machine~$M$ such
  that the following hold.
  \begin{enumerate}
  \item For every~$x,y\in\Sigma^*$, we have~$M(x,y)\in\{x,y\}$, that is, on input~$(x,y)$, the machine~$M$ outputs
    either~$x$ or~$y$.
    \label{it:select}
  \item For every~$x,y\in\Sigma^*$, if at least one of~$x$ and~$y$ is in~$L$, then~$M$ outputs a string in~$L$
    (which must be either~$x$ or~$y$ by~\ref{it:select}).
  \end{enumerate}

  Show that if~$\SAT$ is~$p$-selective, then~$\Poly=\NP$. Hint: use ideas from Exercise~\ref{ex:search}.
\end{exercise}

\end{document}
