\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\\
  Solution
}
\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{solution}
  Let~$L\in\Poly$ be such that~$L\neq\varnothing$ and~$L\neq\Sigma^*$. Then there exists~$x_L\in L$
  and~$y_L\in\Sigma^*\setminus L$. Since~$\Poly\subseteq\NP$, it follows that~$L\in\NP$.

  Let now~$L'\in\NP$ be an arbitrary language in~$\NP$ and let us show that~$L'\leq_p L$.

  Since we suppose~$\Poly=\NP$, we know that there exists a polynomial-time Turing machine~$M$
  deciding~$L'$. Consider then the algorithm~$R$ that runs~$M$ in its input and outputs~$x_L$ if~$M$ accepts and
  outputs~$y_L$ if~$M$ rejects. Clearly~$R$ runs in polynomial time. Furthermore, we clearly have~$R(x)\in L$
  if and only if~$x\in L'$, hence~$R$ is a polynomial-time reduction of~$L'$ to~$L$.

  Therefore~$L$ is~$\NP$-complete.
\end{solution}

\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)$.
    \label{it:NTIME}
  \item Show directly (not by reduction from another known~$\NP$-complete language) that~$K$
    is~$\NP$-complete.
    \label{it:NPcomplete}
  \end{enumerate}
\end{exercise}

\begin{solution}
  For item~\ref{it:NTIME}, let~$N$ be the non-deterministic Turing machine that on input~$(M,x,1^t)$,
  simulates~$M$ on~$x$ for~$t$ steps, accepting if~$M$ accepts (we assume that~$M$ is single-taped, so it can
  be simulated by~$N$).

  Clearly~$N$ decides~$K$ in time~$O(t + \lvert x\rvert)$, which is~$O(n)$. By linear acceleration, we
  get~$K\in\NTIME(n)$.

  \medskip

  For item~\ref{it:NPcomplete}, we have already proved that~$K\in\NTIME(n)\subseteq\NP$, so it remains to show
  that every~$\NP$ language is polynomially reducible to~$K$.

  Fix an~$\NP$ language~$L$. Then there exists an~NTM~$N$ deciding~$L$ in time~$n^k$ for some~$k\in\NN_+$.

  Consider then the (deterministic) algorithm~$R$ that on input~$x$ outputs~$(N,x,1^{\lvert x\rvert^k})$. Note
  that one such~$R$ can be made in time~$O(\lvert x\rvert^k)$, i.e., in polynomial time. Note also
  that~$R(x)\in K$ if and only if~$x$ is accepted by~$N$ in time~$\lvert x\rvert^k$, which is if and only
  if~$x\in L(N) = L$ as~$N$ is~$n^k$-time bounded. Hence~$R$ reduces~$L$ to~$K$.

  Therefore~$K$ is~$\NP$-complete.
\end{solution}

\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{solution}
  Suppose~$\SAT\in\Poly$, that is, suppose there exists a polynomial-time Turing machine~$M$ that
  decides~$\SAT$.

  Without loss of generality, we assume that all variables in the input appear in the formula (this is easy to
  detect and treat in polynomial time). Consider the following algorithm.

  \begin{algorithm}[H]
    \caption{Finding an assignment in~$\SAT$.}
    \DontPrintSemicolon
    Given a formula~$\phi$ on the variables~$x_1,\ldots,x_n$, do the following.\;
    Run~$M$ on~$\phi$.\;
    \lIf{$M$ rejects}{Reject.}
    \Else{
      $\phi_0\leftarrow\phi$.\;
      \For{$i\leftarrow 1$ \KwTo $n$}{
        Let~$\psi$ be the formula obtained from~$\phi_{i-1}$ by assigning~$x_i$ to~$1$ (i.e., true) and
        simplifying.\;
        Run~$M$ on~$\psi$.\;
        \If{$M$ accepts}{
          $a_i\leftarrow 1$.\;
          $\phi_i\leftarrow\psi$.\;
        }
        \Else{
          $a_i\leftarrow 0$.\;
          Let~$\phi_i$ be the formula obtained from~$\phi_{i-1}$ by assigning~$x_i$ to~$0$ (i.e., false) and
          simplifying.\;
        }
      }
    }
    \Return $(a_1,\ldots,a_n)$.\;
  \end{algorithm}

  It is easy to see by induction that in the loop of the algorithm the formula~$\phi_i$ is always satisfiable
  and is obtained from~$\phi$ by assigning some variables to fixed values. From this it follows that if a
  satisfying assignment exists, the algorithm finds it (and of course the algorithm rejects formulas not
  in~$\SAT$).

  Note also that assigning values and simplifying formulas can be done in polynomial time, so the algorithm
  above runs in polynomial time (as it runs~$M$ a total of~$n$ times).
\end{solution}

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

\begin{solution}
  Suppose~$\SAT$ is~$p$-selective and let~$M$ be a polynomial-time Turing machine with the properties
  of~$p$-selection for~$\SAT$.

  Consider the following algorithm. (We again assume that all variables appear in~$\phi$.)

  \begin{algorithm}[H]
    \caption{Finding an assignment in~$\SAT$.}
    \DontPrintSemicolon
    Given a formula~$\phi$ on the variables~$x_1,\ldots,x_n$, do the following.\;
    $\phi_0\leftarrow\phi$.\;
    \For{$i\leftarrow 1$ \KwTo $n$}{
      Let~$\psi^\top$ and~$\psi^\bot$ be the formulas obtained from~$\phi_{i-1}$ by assigning~$x_i$ to~$1$
      and~$0$ respectively and simplifying.\;
      Run~$M$ on~$(\psi^\top,\psi^\bot)$.\;
      \If{$M$ returns~$\psi^\top$}{
        $a_i\leftarrow 1$.\;
        $\phi_i\leftarrow\psi^\top$.\;
      }
      \Else{
        $a_i\leftarrow 0$.\;
        $\phi_i\leftarrow\psi^\bot$.\;
      }
    }
    \lIf{$(a_1,\ldots,a_n)$ is a satisfying assignment}{Accept.}
    \lElse{Reject.}
  \end{algorithm}

  Since the algorithm above runs~$M$ a total of~$n$ times and all constructions and tests done by the
  algorithm are polynomial, it follows that the algorithm is polynomial.

  Clearly if~$\phi\notin\SAT$, then the algorithm above rejects~$\phi$ as no assignment satisfies~$\phi$.

  Suppose then that~$\phi\in\SAT$. It is easy to see by induction that the~$p$-selection property of~$M$
  implies that each~$\phi_i$ is satisfiable. Since~$\phi_i$ is obtained from~$\phi$ by
  assigning~$x_j\leftarrow a_j$ for every~$j\in\{1,\ldots,i\}$, it follows that~$\phi_n =
  \phi(a_1,\ldots,a_n)$ and~$\phi_n$ is tautologically true, hence the algorithm accepts~$\phi$.

  Therefore the algorithm decides~$\SAT$ in polynomial time, which implies~$\SAT\in\Poly$.

  Since~$\SAT$ is~$\NP$-complete, this implies that~$\Poly=\NP$.
\end{solution}

\end{document}