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

\begin{document}
\psetnum{6}
\date{2004/12/02}

\begin{pset}
  \begin{problem}
    % 8.18 - nesting of ()[]
    Let $B$ be the language of properly-nested parentheses and
    brackets. We show that $B$ is in $\L$. The following procedure
    decides whether a string of parentheses and brackets is properly
    nested:

    We first scan over the string from left to right, maintaining a
    counter of the current depth. Every time we encounter a
    `\texttt{(}' or `\texttt{[}' character, we increment the counter,
    and every time we encounter a `\texttt{)}' or `\texttt{]}', we
    decrement the counter. If at any time the counter goes negative,
    or if the counter is not equal to zero once the end of the string
    is reached, we reject. If neither happens, then we have ensured
    that the string is a properly nested sequence, ignoring the
    distinction between parentheses and brackets. Note that this phase
    requires only a logarithmic amount of space, since we need only
    maintain the counter. Since the input string is of length $n$, it
    contains at most $n$ open parentheses or brackets, so the counter
    fits in $\bigO{\log n}$ bits.

    We next need to ensure that each open parenthesis or bracket is
    associated with a close symbol of the same type. To check whether
    the $i$th open symbol is associated with a close symbol of the
    same type, we first scan over the string counting open symbols
    until we find the $i$th. We then record the type of this symbol.
    We initialize a depth counter to zero and scan through the string
    from the current position, incrementing and decrementing it when
    we encounter open and close symbols as before. When we encounter a
    close symbol and the depth counter is zero, we have found the
    close symbol associated with the $i$th open symbol. If the open
    and close symbols are not of the same type, we reject. Note that
    this requires only logarithmic space, for the same reason. We
    perform this check for all values of $i$ from 1 to the number of
    open parentheses (which is $\bigO{n}$), and we can reuse the
    space, so this can be performed for all $i$ in logarithmic
    space. If all of these checks pass, we accept. This accepts all
    properly nested parentheses and brackets, so the problem is in
    $\L$.
  \end{problem}

  \begin{problem}
    % 8.22 - ADD/PAL-ADD
    \begin{subproblem}
      To check whether $\tup<x,y,z> \in ADD$, we need to verify the
      addition $x + y = z$. We can do this using logarithmic space. We
      will do so by verifying each bit of the addition in turn. Let
      $x_i$ be the $i$th lowest order bit, and similarly $y_i$ and
      $z_i$. We also maintain a single bit $c$ to track the carry
      state, which is initially zero. Then for each $i$ from 1 to the
      number of bits in the input numbers, we add the bits $x_i + y_i
      + c$. The result is a two-bit integer. The high bit is the new
      value for $c$, and the low bit should equal $z_i$. If at any
      time the low bit does not equal the corresponding $z_i$, then
      $x+y \neq z$, and we reject. Otherwise, if the loop completes
      without rejecting, we accept.

      This algorithm requires logarithmic space. Performing
      bit-addition requires constant space, as does holding the carry
      bit $c$. So the space bound is dominated by the requirement for
      holding the counter $i$. The value of $i$ is bounded above by
      the number of bits in each input integer, which is $\bigO{n}$,
      so $i$ requires $\bigO{\log n}$ bits. Thus $ADD \in \L$.
    \end{subproblem}

    \begin{subproblem}
      We can also check whether $x + y$ is a palindrome using
      logarithmic space. Let $z$ be the sum, and let $m$ be the number
      of digits in it. (Note that $m = \bigTheta{n}$, and that we can
      determine $m$ using logarithmic space by performing the addition
      without keeping track of the result, simply counting the number
      of bits required.) As before, let $z_i$ be the $i$th lowest
      order bit of $z$. If $z$ is a palindrome, then $z_i =
      z_{m-i+1}$.

      Our algorithm is to check, for each $k$ from $1$ to
      $\frac{m}{2}$, whether $z_k = z_{m-k+1}$. We can do so in much
      the same method as verifying an addition in $ADD$. We maintain a
      carry bit $c$ initially equal to zero. Then for each $i$ from 1
      to $m$, we add the bits $x_i + y_i + c$. The result is $z_i$. If
      $i = k$ or $i = m-k+1$, we save $z_i$ in a register. Once we
      have iterated over all $i$, we reject if $z_k \neq z_{m-k+1}$.
      As before, for each $k$, this requires only constant space plus
      logarithmic space for keeping track of $i$. Performing this
      check for all $k$ also requires logarithmic space, since the
      space for each iteration can be reused. If we have iterated over
      all $k$ without rejecting, then $z$ is a palindrome, and we
      accept. So $PAL-ADD \in \L$.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    % 8.26 - STRONGLY-CONNECTED
    \begin{lemma}
      \textit{STRONGLY-CONNECTED} $\in \NL$.
    \end{lemma}
    \begin{proof}
      We show that \textit{STRONGLY-CONNECTED} is in $\coNL$. We
      nondeterministically guess two vertices in the graph that are
      not connected. We then verify that there is no path between
      these vertices. We can do this using logarithmic space because
      \textit{PATH} $\in \coNL$. So \textit{STRONGLY-CONNECTED} $\in
      \coNL = \NL$.
    \end{proof}
    
    \begin{theorem}
      \textit{STRONGLY-CONNECTED} is $\NL$-hard. 
    \end{theorem}
    \begin{proof}
      We reduce \textit{PATH} to \textit{STRONGLY-CONNECTED}. Let
      $\tup<G,s,t>$ be an instance of \textit{PATH}. Generate a new
      graph $G'$ that is identical to $G$ except that for every vertex
      $v$ there is an edge $(v \to s)$ and an edge $(t \to v)$. Then
      $\tup<G,s,t> \in$ \textit{PATH} iff $\tup<G',s,t> \in$
      \textit{STRONGLY-CONNECTED}. First, if there is a path from $s$
      to $t$ in $G'$, then $G'$ is strongly connected. For any pair of
      vertices $\tup<u,v>$, there is a path $u \to s \to t \to v$. If
      $\tup<G,s,t> \notin$ \textit{PATH}, there is no path from $s$ to
      $t$ in $G$, and this remains true in $G'$. So $\tup<G',s,t>
      \notin$ \textit{STRONGLY-CONNECTED}.

      It is easy to see that this reduction can be performed using a
      log-space transducer. The transducer simply outputs the same
      graph $G$, then iterates over all vertices $v$ adding the $(v
      \to s)$ and $(t \to v)$ edges. This requires only logarithmic
      space on the work tape to keep track of the index of $v$. So
      \textit{STRONGLY-CONNECTED} is $\NL$-hard.
    \end{proof}
    
    \begin{corollary}
      \textit{STRONGLY-CONNECTED} is $\NL$-complete.
    \end{corollary}
    \begin{proof}
      It is $\NL$-hard and in $\NL$, so it is $\NL$-complete.
    \end{proof}
  \end{problem}

  \begin{problem}
    % A_LBA
    \begin{subproblem}
      $A_\LBA$ is $\PSPACE$-complete. Furthermore, the reduction from
      any problem in $\PSPACE$ to $A_\LBA$ requires polynomial space;
      i.e. it can be computed by a log-space transducer. Thus if it is
      in $\NL$, then every problem in $\PSPACE$ is also in $\NL$. We
      know there are problems in $\PSPACE$ that are not in $\NL$ by
      the hierarchy theorems. So $A_\LBA \notin \NL$.
    \end{subproblem}

    \begin{subproblem}
      If $A_\LBA \in \P$, then every problem in $\PSPACE$ is in
      $\P$. It is not currently known whether this is the case, so it
      is unknown whether $A_\LBA \in \P$.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    % 9.18/9.19 - NEXPTIME
    \begin{subproblem}
      \begin{theorem}
        If $A \in \TIME{n^6}$ then $pad(A, n^2) \in \TIME{n^3}$.
      \end{theorem}
      \begin{proof}
        Suppose $A \in \TIME{n^6}$. Then we will show how to decide
        whether a string $B$ of length $n$ is in $pad(A,n^2)$ in
        $\bigO{n^3}$ time. Observe that to be in $pad(A,n^2)$, $B$
        must consist of a substring $s$ of length $\sqrt{n}$ followed
        by $(n-\sqrt{n})$ `\texttt{\#}' symbols. We can easily verify
        that this is the case by scanning over $B$ (in linear time).
        Then $B \in pad(A,n^2)$ if and only if $s$ is in $A$. Since
        the string $s$ has length $\sqrt{n}$, and $A \in \TIME{n^6}$,
        deciding $s \in A$ requires $\bigO{\left(\sqrt{n}\right)^6} =
        \bigO{n^3}$ time. Thus, $pad(A, n^2) \in \TIME{n^3}$.
      \end{proof}
    \end{subproblem}

    \begin{subproblem}
      \begin{theorem}
        If $\NEXPTIME \neq \EXPTIME$, then $\P \neq \NP$.
      \end{theorem}
      \begin{proof}
        Suppose there is some language $L$ that is in $\NEXPTIME$ but
        not in $\EXPTIME$. Then $L \in \NTIME{2^{n^k}}$ for some $k$.
        By the same reasoning as above, if $L \in \NTIME{2^{n^k}}$
        then $pad(L, 2^{n^k}) \in \NTIME{n}$. So $pad(L, 2^{n^k}) \in
        \NP$.

        If $\P = \NP$, then $pad(L, 2^{n^k}) \in \TIME{n^l}$ for some
        $l$. But then we can solve $L$ by padding the input to length
        $2^{n^k}$ and solving the resulting problem. This requires
        time $\bigO{n^l}$ in the size of the padded problem, so time
        $\bigO{\left(2^{n^k}\right)^l} = \bigO{2^{n^{kl}}}$. Thus $L
        \in \EXPTIME$. But we defined $L$ to not be in $\EXPTIME$. So
        $\P \neq \NP$ unless $\NEXPTIME = \EXPTIME$.
      \end{proof}
    \end{subproblem}
  \end{problem}

  \begin{problem}
    % unique-sat
    \begin{theorem}
      \textit{UNIQUE-SAT} $\in \P^{SAT}$
    \end{theorem}
    \begin{proof}
      Let $\phi$ be a Boolean formula. We give a polynomial-time
      procedure for determining whether $\phi$ has a unique satisfying
      solution using a \textit{SAT} oracle.

      First, we query the oracle with $\phi$ to determine whether
      $\phi \in SAT$. If not, we reject, since it has no satisfying
      solution at all. If it does, we then determine what the
      satisfying solution is. We do so one variable at a time.

      Let $x_1, x_2, \cdots, x_m$ be the variables in $\phi$. Suppose
      that we have determined the values of all variables with index
      less than $i$. We try both possibilities for variable $x_i$
      (true or false) to determine which one leads to a satisfying
      assignment. To test whether a particular assignment leads to a
      satisfying assignment, we add clauses to $\phi$ to force
      variable assignments: for each $l$, if $x_l$ is assigned to be
      true, we add the clause ``$\wedge x_l$'', and if it assigned to be
      false, we add the clause ``$\wedge \overline{x_l}$''. We query
      the \textit{SAT} as to whether $\phi$ with forcing clauses for
      all variables with index $\le i$ is satisfiable; if so, then a
      satisfying assignment with these variable assignments
      exists. This determines a value of $x_i$ in a satisfying
      assignment. We repeat this process for $i$ from $1$ to $m$, to
      find a satisfying assignment for all variables. Note that this
      process requires $\bigTheta{m} = \bigO{n}$ time and space.

      Now we determine whether there exists any \emph{other}
      satisfying assignment for $\phi$. We do so by augmenting $\phi$
      with a new clause containing $\overline{x_i}$ if $x_i$ is true
      in the satisfying assignment we found, and $x_i$ if $x_i is
      false$. (For example, ``$\wedge ( \overline{x_1} \vee
      \overline{x_2} \vee x_3 \vee x_4 )$'' if $x_1$ and $x_2$ are
      true and $x_3$ and $x_4$ in the satisfying assignment.) This
      forces at least one variable to take a different value. We then
      query the \textit{SAT} oracle with this augmented formula. If it
      returns true, we reject; otherwise we accept. The oracle accepts
      only if there is a satisfying assignment with some variable
      different, i.e. if the satisfying assignment is non-unique. So
      \textit{UNIQUE-SAT} $\in \P^{SAT}$. 
    \end{proof}
  \end{problem}
\end{pset}
\end{document}