\documentclass{article}
\input{6840-preamble}

\begin{document}
\psetnum{5}
\date{2004/11/18}

\begin{pset}
  \begin{problem}
    \begin{theorem}
      Any language $A \in \P \setminus \set{A = \varnothing,
        A=\Sigma^*}$ is $\NP$-complete if $\P = \NP$.
    \end{theorem}

    \begin{proof}
      Let $A$ be a language in $\P$ that is not $\varnothing$ or
      $\Sigma^*$. Note that there are therefore strings $\aleph \in A$
      and $\beth \notin A$.
      
      We give a reduction from $SAT$ to $A$ to show that
      $A$ is $\NP$-complete. Suppose $\phi$ is an instance of
      $SAT$. Our reduction is as follows:

      \begin{enumerate}
      \item Solve $\phi$. This can be done in polynomial time, since
        $\P = \NP$.
      \item If $\phi$ is solvable, let $\psi_\phi = \aleph$. If it is not,
        let $\psi_\phi = \beth$.
      \item Output $\psi_\phi$.
      \end{enumerate}

      The reduction runs in polynomial time, and if $\phi$ is solvable
      it outputs $\aleph \in A$, and $\beth \notin A$ if not. Thus,
      $SAT$ is reduced to $A$, and $A$ is NP-complete. So every
      language in $\P \setminus \set{A = \varnothing, A=\Sigma^*}$ is
      $\NP$-complete if $\P = \NP$.
    \end{proof}
  \end{problem}

  \begin{problem}
    % minimizing NFAs
    \begin{theorem}
      For a CNF-formula $\phi$ with $m$ variables and $c$ clauses,
      there is a $\NFA$ with $\bigO{cm}$ states that accepts all
      non-satisfying assignments, represented as $m$-length Boolean
      strings.
    \end{theorem}

    \begin{proof}
      Let $\phi$ be given as above. We give a $\NFA$ $N$ that accepts
      non-satisfying assignments of $\phi$. The $\NFA$ contains $c$
      ``sub-machines'', corresponding to each clause of $\phi$. For
      each clause $\mathfrak{c}$, we create a state $\Game_{\mathfrak{c},i}$
      corresponding to the variable $x_i$ ($1 \le i \le m$), plus an
      accept state $\Game_{c,m+1}$. We connect $\Game_{\mathfrak{c},i}$ to
      $\Game_{\mathfrak{c},i+1}$ with a $\mathtt{0}$ transition if variable $x_i$
      appears non-negated in clause $\mathfrak{c}$, with a $\mathtt{1}$
      transition if variable $x_i$ appears negated in clause $\mathfrak{c}$, and
      with both if $x_i$ does not appear in $\mathfrak{c}$. We then create a
      start state that is connected by a $\epsilon$-transition to all
      of the states $\Game_{\mathfrak{c},1}$.

      This uses $m+1$ states per each of the $c$ clauses, plus the
      start state, so the number of states is $\bigO{cm}$.

      This $\NFA$ gives the correct result. It accepts if the sequence
      of assignments given by the input does not satisfy one of the
      clauses in $\phi$, and therefore does not satisfy $\phi$; it
      rejects otherwise.
    \end{proof}

    \begin{corollary}
      $\NFA$s cannot be minimized in polynomial time unless $\P =
      \NP$. 
    \end{corollary}

     \begin{proof}
       Suppose $\NFA$s can be minimized in polynomial time. Then $3SAT
       \in \P$, so $\P = \NP$.
     \end{proof}
  \end{problem}

  \begin{problem}
    % EQ_REX
    \begin{lemma}
      Any regular expression $R$ can be converted to a $\NFA$ $N$ with
      $n$ states in polynomial time, where $n$ is polynomial in
      $\abs{R}$.
      \label{lem:rex-nfa}
    \end{lemma}

    \begin{proof}
      (The proof is routine; we give only an outline.) The procedure
      for performing the conversion is precisely that given in Sipser,
      Lemma 1.29. Note that for each of the six cases in the
      definition of the regular expression, the construction procedure
      requires time polynomial in the length of the regular
      expression, and increases the size of the resulting $\NFA$ only
      polynomially.
    \end{proof}

    \begin{lemma}
      $EQ_\NFA \in \PSPACE$
      \label{lem:eq-nfa}
    \end{lemma}

    \begin{proof}
      Suppose we are given two $\NFA$s $N_1$ and $N_2$. We
      nondeterministically guess an input sequence which one of the
      $\NFA$s accepts and the other rejects, and simulate $N_1$ and
      $N_2$ on it with a $\NTM$. The input sequence may be arbitrarily
      long (i.e. not polynomial in the size of $N_1$ and $N_2$), but
      it does not have to be written to tape; the $\NTM$ can
      non-deterministically guess each symbol in the sequence in turn
      while simulating the $\NFA$s. Once the full input sequence is
      simulated, we verify whether one $\NTM$ is in an accept state
      and the other is not. Thus, $\overline{EQ_\NFA}$ is in
      \textsf{NPSPACE}. Hence, by the Immerman-Szelepcsenyi theorem,
      $EQ_\NFA$ is in $\mathsf{NPSPACE} = \PSPACE$.
    \end{proof}
    
    \begin{theorem}
      $\mathit{EQ}_\REX \in \PSPACE$
    \end{theorem}

    \begin{proof}
      Suppose we are given two $\REX$s $R_1$ and $R_2$. By
      Lemma~\ref{lem:rex-nfa}, we can convert these to equivalent
      $\NFA$s $N_1$ and $N_2$ in polynomial time and space that have
      size polynomial in the length of their respective $\REX$s. We
      simply test whether $\tup<N_1, N_2> \in EQ_\NFA$. The length of
      $\tup<N_1, N_2>$ is polynomial in the length of the input, so
      performing this test can be done using polynomial space, by
      Lemma~\ref{lem:eq-nfa}. So    $\mathit{EQ}_\REX \in \PSPACE$.
    \end{proof}
  \end{problem}

  \begin{problem}
    % go-moku
    \begin{theorem}
      $GM \in \PSPACE$
    \end{theorem}

    \begin{proof}
      Go-moku is clearly a combinatorial game, we can use the standard
      approach of inspecting the game tree to identify winning
      strategies. Note that polynomial space is required to check
      whether any player has won in a given configuration, since we
      can simply test all of the possible 5-lines individually. We
      need only bound the depth of the game tree.

      \begin{lemma}
        At most $n^2$ moves can be made from any board position.
        \label{lem:gm-moves}
      \end{lemma}

      \begin{proof}
        Markers can never be removed after they are placed. The board
        is $n \times n$, so it has $n^2$ spaces. Each player places a
        marker on every move. It is therefore not possible to make
        more than $n^2$ moves, even if the board starts empty.
      \end{proof}

      \begin{corollary}
        The maximum depth of the game tree is polynomial in $n$.
      \end{corollary}
      \begin{proof}
        Immediate from Lemma~\ref{lem:gm-moves}.
      \end{proof}

      A representation of the board position is polynomial in $n$,
      since we simply need to store the state of each of the $n^2$
      squares. So we can store the game history in space polynomial in
      $n$, since the size of this is simply the size of the board
      position multiplied by the depth of the game tree. We need only
      keep a representation of the game history when testing all
      possible outcomes in the game tree to check whether there is a
      winning strategy, so polynomial space is required. Thus $GM \in
      \PSPACE$. 
    \end{proof}
  \end{problem}

  \begin{problem}
    % happy-cat
    \begin{theorem}
      \textit{HAPPY-CAT} $\in \P$.
    \end{theorem}

    \begin{proof}
      The game is combinatorial, so we can generate and scan the game
      tree to determine whether the Cat player has a winning
      strategy. The game tree is exponential in size, but we do not
      need to consider all of it:

      $\bigO{n^2}$ possible game states must be examined. Each of the
      two players can be on any of the $n$ vertices of the graph, and
      either of the two players may be next up to move. So there are
      $2n^2$ game states. Recall that the game is defined so that
      it ends in a draw if both players are in the same position and
      it is the same player's turn to move as a previous game
      state. Thus, no game state needs to be examined twice when
      traversing the game tree, since this gives an immediate draw. So
      inspecting the game tree to determine whether the cat player has
      a winning strategy takes $\bigO{n^2}$ time, and
      \textit{HAPPY-CAT} $\in \P$.
    \end{proof}
  \end{problem}

  \begin{problem}
    % min-formula
    \begin{subproblem}
      \begin{definition}
        \textit{EQ-FORMULA} = $\set{\phi_1, \phi_2 | \phi_1 \text{ and
          } \phi_2 \text{ are equivalent formulas}}$
      \end{definition}

      \begin{lemma}
        $\overline{\text{\textit{EQ-FORMULA}}} \in \NP$
      \end{lemma}
      \begin{proof}
        Let the certificate be an assignment of variables such that
        $\phi_1$ and $\phi_2$ differ. We can compute in polynomial
        time the values of $\phi_1$ and $\phi_2$ for this assignment
        and thereby verify the certificate.
      \end{proof}
      \begin{corollary}
        \textit{EQ-FORMULA} $\in \coNP \subseteq \PSPACE $
      \end{corollary}
      
      \begin{theorem}
        \textit{MIN-FORMULA} $\in \PSPACE$
      \end{theorem}
      
      \begin{proof}
        Given a formula $\phi$, we give a procedure for determining
        whether there is a shorter formula $\phi'$ equivalent to
        $\phi$:
        for every formula $\eth$ shorter than $\phi$, we check whether
        $\tup<\phi,\eth> \in $ \textit{EQ-FORMULA}. If any such $\eth$
        exists, we reject; otherwise, we accept. Since
        \textit{EQ-FORMULA} $\in \PSPACE$, each check can be done using
        polynomial space in $\abs{\phi}$. Indeed, the entire procedure
        requires only polynomial space, since we simply need to store
        on the tape the current formula $\eth$ being processed,
        process it, then find the next $\eth$ and overwrite the
        tape. So \textit{MIN-FORMULA} $\in \PSPACE$
      \end{proof}
    \end{subproblem}

    \begin{subproblem}
      It is true that a $\NTM$ can verify that $\phi \notin $
      \textit{MIN-FORMULA} by guessing the smaller equivalent formula
      $\phi'$. However, it cannot necessarily do so \emph{in
        polynomial time}. Once it has guessed the formula, it must
      verify that it is equivalent: it must check whether $\tup<\phi,
      \phi'> \in$ \textit{EQ-FORMULA}. We showed, however, that
      \textit{EQ-FORMULA} was in $\coNP$, not that it was in $\NP$, so
      the $\NTM$ cannot necessarily perform this computation in
      polynomial time. So this proof fails to show that
      \textit{MIN-FORMULA} $\in \coNP$.
      
    \end{subproblem}
  \end{problem}
\end{pset}
\end{document}