\documentstyle[11pt,fullpage]{article}
\begin{document}
\input{preamble.tex}
\lecture{9}{March 10, 1998}{Daniel A. Spielman}{Venkatesan Guruswami}
\section{Introduction}
For every known NP-complete problem, the number of solutions over its
instances varies over a large range, from zero to exponentially
many. It is therefore natural to ask if the inherent intractability
of NP-complete problems is caused by this wide variation in the number
of possible solutions.

In this lecture we establish that the answer to this question is NO.
In particular, we establish a result of Valiant and Vazirani~\cite{VV}
stating that deciding the satisfiability of SAT instances that are
promised to have at most one satisfying assignment (let us call such
instances as USAT instances in the sequel) is as difficult as deciding
satisfiability of general SAT instances.

This is proved by exhibiting a randomized reduction from SAT to USAT,
i.e we establish a randomized polynomial-time TM $M$ such that if
\begin{eqnarray*}
\phi \notin {\rm SAT} & \Longrightarrow & M(\phi) \notin {\rm SAT} \mbox{
(and hence } M(\phi) \notin {\rm USAT}) \\
\phi \in {\rm SAT} & \Longrightarrow & {\rm Prob}\big[M(\phi) \in {\rm
USAT}\big] \ge \frac{1}{8}
\end{eqnarray*}
where the probability is taken over the internal coin tosses of the
machine $M$.

The above implies that if there exists a polynomial-time randomized
algorithm for distinguishing instances of SAT having zero or one
satisfying assignment, then we will have ${\bf NP} = {\bf RP}$, since
we can give a {\bf RP} algorithm for SAT by first employing the above
reduction $M$ and then using the supposed algorithm for deciding USAT.

To give the above reduction, we will now develop some machinery from
Universal Hashing which will also be useful in several other places.

\section{Universal Hashing}
This extremely useful tool was developed by Carter and Wegman. \\
\begin{definition}
{\sf (Universal Hashing)}: Given sets $S$ and $T$, a
family ${\cal H}$ of functions from $S$ to $T$ is a {\em universal
family of hash functions} from $S$ to $T$ if
\begin{itemize}
\item $\forall x \in S$, $\forall w \in T$
\[ {\rm Prob}_{h \in {\cal H}} \big[ h(x) = w \big] = \frac{1}{|T|}
\mbox{      (uniformity)} \]
\item $\forall x  \neq y \in S$, $\forall w,z\in T$,
\[  {\rm Prob}_{h \in {\cal H}} \big[ (h(x)=w) \wedge (h(y)=z)
\big] = \frac{1}{|T|^2} \mbox{     (universal independence)} \]
\end{itemize}
\end{definition}

\noindent {\bf An example of a universal hash family}: Let
$S=\{0,1\}^n$, $T=\{0,1\}^k$, and for $x \in \{0,1\}^n$, let
$h_{M,b}(x) = Mx + b$ where $M$ is a $k \times n$ boolean matrix, $b$
is a column vector in $\{0,1\}^k$ and all operations are mod 2. The
family ${\cal H}$ is the set of functions $h_{M,b}$ for all possible
values of $M$ and $b$.

\begin{proposition}
${\cal H} = \{h_{M,b}\}$ is a universal family of hash functions from
$\{0,1\}^n$ to $\{0,1\}^k$.
\end{proposition}
\noindent {\bf Proof:} We first check universality. For any fixed $x
\in \{0,1\}^n - \vec{0}$ and $y \in \{0,1\}^k$ (the case $x=\vec{0}$
is trivial)
\begin{eqnarray*}
{\rm Prob}_{h \in {\cal H}}\big[h(x)=y\big] & = & {\rm
Prob}_{M,b}\big[ Mx + b = y\big] \\ 
& = & \sum_{z \in \{0,1\}^k} {\rm Prob}_{M} \big[ Mx = z \big] \cdot
{\rm Prob}_{b} \big[ b = y - z\big]\\
& = & 2^k \cdot 2^{-k} \cdot 2^{-k} \\ & = & 2^{-k}
\end{eqnarray*}
To check universal independence, for $x \neq y \in \{0,1\}^n$ and $w,z
\in \{0,1\}^k$, we have
\begin{eqnarray*}
{\rm Prob}_{h \in {\cal H}}\big[(h(x)=w) \wedge (h(y)=z)\big] & = & {\rm
Prob}_{M,b}\big[ Mx + b = w \wedge My + b = z\big] \\ 
& = & {\rm Prob}_{M,b}\big[ M(x-y) = w-z \wedge Mx+ b = w \big] \\
& = & {\rm Prob}_{M} \big[ M(x-y) = w-z \big] \times \\
& & {\rm Prob}_{M,b}
\big[  Mx+ b = w \ | \ M(x-y) = w-z \big] \\
& = & 2^{-k} \times {\rm Prob}_{M,b} \big[ Mx+b = w \big] \\
& = & 2^{-k} \cdot 2^{-k} \\
& = & 2^{-2k}
\end{eqnarray*}
where the fourth equality follows since $M$ is a random $k \times n$
matrix and $x-y$ is a fixed non-zero vector and the events $Mx+b=w$
and $M(x-y)=w-z$ are independent because of the random and independent
(from $M$) choice of $b$. The next equality follows from the
universality property proved earlier.  {\hfill $\Box$}

We now prove that we do not need the random vector $b$ if $x,y \neq
\vec{0}$.

\begin{proposition}
$\forall x \neq y \in \{0,1\}^n - \vec{0}$ and $\forall w,z \in
\{0,1\}^k$, we have
\[ {\rm Prob}_{M} \big[ Mx = w \wedge My = z \big] =
\frac{1}{2^{2k}}. \]
\end{proposition}
\noindent {\bf Proof:} 
If $x$ and $y$ are $e_{1}=(1,0,\ldots,0)$ and $e_{2} =
  (0,1,0,\ldots,0)$, respectively, then the truth of the
  proposition is clear.
Since neither $x$ nor $y$ is $\vec{0}$, they are linearly independent.
Thus, there exists rank $n$ matrix $A$ such that $Ax =
  e_{1}$ and $Ay = e_{2}$.
Because the matrix $A$ has full rank, the distribution
  obtained by multiplying a unformly chosen random matrix
  $M$ by
  $A$ is the same as that obtained by just choosing $M$
  uniformly at random.
So, the truth of the proposition for $e_{1}$ and $e_{2}$
  implies the truth of the proposition in general.{\hfill $\Box$}
%Let $A$ denote the set of indices $i$ at which
%$x_i =y_i$. Let $x_A$ (resp $y_A$) denote the vector $x$ (resp $y$)
%projected onto indices in $A$, and let $M_A$ denote the matrix
%obtained by retaining those columns whose index is in $A$. By
%definition we have $x_A = y_A$.

%Now $Mx = M_A x_A + M_{\bar{A}} x_{\bar{A}}$, and, $My = M_A y_A +
%M_{\bar{A}} y_{\bar{A}}$, and $M_A x_A=M_A y_A$. Assume for the moment
%that $x_{\bar{A}} \neq \vec{0}$ and $y_{\bar{A}} \neq \vec{0}$. Now
%$M_{\bar{A}} x_{\bar{A}}$ and $M_{\bar{A}} y_{\bar{A}}$ are adding
%disjoint sets of columns of $M$ and hence the probability that the
%corresponding columns of $M$ add up to any particular vector are
%independent of each other and each has a probability $2^{-k}$ of
%occurring, giving an overall probability of $2^{-2k}$.

%In the case when $x_{\bar{A}} = \vec{0}$, we have $x_A \neq \vec{0}$
%and $y_{\bar{A}} \neq \vec{0}$ and $Mx=w \wedge My=z$ is equivalent to
%$M_A x_A = w \wedge M_{\bar{A}} y_{\bar{A}} = z - w$, and this happens
%with probability $2^{-2k}$ since the sets of columns of $M$ being
%considered are disjoint as before. 


\begin{proposition}
\label{main-prop}
Let $S \subseteq \{0,1\}^n$ with $2^{k-2} \le |S| \le 2^{k-1}$. Then,
\[ {\rm Prob}\big[ \exists \ ! \ s \in S \mbox{ s.t } Ms=\vec{0} \big] \ge
\frac{1}{8} \]
where the probability is taken over the uniform choice of $M$ from the
set of all $k \times n$ boolean matrices.
\end{proposition}
\noindent {\bf Proof:} The proof proceeds by distinguishing two cases.

\noindent {\sf Case 1}: $\vec{0} \in S$. In this case $M \vec{0} =
\vec{0}$
\begin{eqnarray*}
{\rm Prob}_{M} \big[ \exists s \in S, s \neq \vec{0}, Ms =\vec{0}
\big] & \le & \sum_{s \in S, s \neq \vec{0}} {\rm Prob}_{M} \big[ Ms =
\vec{0} \big ] \\
& \le & |S| \cdot 2^{-k} \\
& \le & \frac{1}{2}
\end{eqnarray*}
and hence 
\[ {\rm Prob}\big[ \exists ! s \in S \mbox{ s.t } Ms=\vec{0} \big] \ge
\frac{1}{2} \]

\noindent {\sf Case 2}: $\vec{0} \notin S$. Now for any fixed $s \in
S$, ${\rm Prob}_{M}\big[ Ms=\vec{0}\big] = 2^{-k}$ and $\forall t \neq
s \in S$, ${\rm Prob}_{M}\big[ Ms=\vec{0} \wedge Mt=\vec{0} \big] =
2^{-2k}$, which implies ${\rm Prob}_{M}\big[ Mt=\vec{0} \ | \
Ms=\vec{0} \big] = 2^{-k}$. Also,
\begin{eqnarray*}
{\rm Prob}_{M} \big[ Ms = \vec{0} \wedge \forall t \neq s, Mt \neq
\vec{0} \big] & = & {\rm Prob}_{M} \big[ Ms = \vec{0} \big] \cdot {\rm
Prob}_{M} \big[ \forall t \neq s, Mt \neq \vec{0} \ | \ Ms = \vec{0}
\big] \\
& = & 2^{-k} \cdot \left( 1 - {\rm Prob}_{M} \big[ \exists t \neq s
\in S, Mt = \vec{0} \ | \ Ms = \vec{0} \big] \right) \\
& \ge & 2^{-k} \cdot \left( 1 - \sum_{t \in S, t \neq s} {\rm
Prob}_{M} \big[ Mt = \vec{0} \ | \ Ms = \vec{0}\big] \right) \\
& = & 2^{-k} \left( 1 - 2^{-k} (|S|-1) \right) \\
& \ge & 2^{-k-1}.
\end{eqnarray*}
Now,
\begin{eqnarray*}
{\rm Prob}_{M} \big[ \exists s, Ms = \vec{0} \wedge \forall t \neq s
\in S, Mt \neq \vec{0} \big] &  = & 
\sum_{s \in S} {\rm Prob}_{M} \big[ Ms = \vec{0} \wedge \forall t \neq
s, Mt \neq \vec{0} \big] \\
& \ge & |S| \cdot 2^{-k-1} \\
& \ge & \frac{1}{8},
\end{eqnarray*}
where the first equality is because the considered events are all
mutually exclusive.  {\hfill $\Box$}

\section{Deciding USAT in RP-time implies NP=RP}

The idea is the following: Given an instance of SAT we repeatedly
apply restrictions on the formula.  Then we run the {\bf RP} machine
to detect whether the new formula has exactly one solution or not. The
consequence of this is that any {\bf NP} problem will be solved in
{\bf RP} time. Since ${\bf RP} \subseteq {\bf NP}$, this means ${\bf
NP}={\bf RP}$. Note that this will also imply an hierarchy collapse to
the second level.

The successive restrictions are applied as follows. Given a
CNF formula $\phi$ on $n$ variables $\vec{x}$, choose $n+1$ random
vectors $\vec{v}_1,\vec{v}_2,\cdots,\vec{v}_{n+1}$, and create the formulas $\phi_i$ for
$1 \le i \le n+1$ as follows:
\[ \phi_i = \phi \wedge (\vec{x} \cdot \vec{v}_1 = 0) \wedge ( \vec{x}
\cdot \vec{v}_2 = 0) \wedge \cdots \wedge (\vec{x} \cdot \vec{v}_i = 0)
\]

\begin{lemma}
If $\phi$ is not satisfiable, then none of the $\phi_i$'s are satisfiable.
\end{lemma}
\noindent {\bf Proof:} O.K. {\hfill $\Box$}
\begin{lemma}
If $\phi$ is satisfiable, then with probability at least 1/8, at least
one of the $\phi_i$'s has a unique satisfying assignment.
\end{lemma}
\noindent {\bf Proof:} Let $S$ be the set of satisfying assignments of
$\phi$: by hypothesis $|S| \ge 1$. Let $k$ be such that $2^{k-2} \le
|S| < 2^{k-1}$. Then by Proposition~\ref{main-prop}, $\phi_k$ has a
probability $\ge 1/8$ of having exactly one satisfying
assignment. {\hfill $\Box$} \\

The above two lemmas provide the randomized reduction of SAT to
USAT, thus proving that detecting unique solutions is as hard as {\bf
NP}. In complexity--theoretic terms, we have just proved that {\bf NP}
is randomly reducible to {\bf UP} where {\bf UP} is the class of {\em
promise problems} whose instances are promised to have either zero or one
solution. Put more succinctly, the main results are 
\begin{theorem}
${\bf NP} \subseteq {\bf RP}^{\bf UP}$.
\end{theorem}

\begin{theorem}
If ${\bf UP} \subseteq {\bf RP}$, then ${\bf NP} = {\bf RP}$.
\end{theorem}

\begin{thebibliography}{99}
\bibitem{VV} L.~G.~Valiant and V.~V.~Vazirani, NP is as easy as
detecting unique solutions, {\em Theoretical Computer Science}, {\bf
47} (1986), pp. 85-93.
\end{thebibliography}
\end{document}