\documentstyle[twoside]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}


%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
  \pagestyle{myheadings}
  \thispagestyle{plain}
  \newpage
  \setcounter{lecnum}{#1}
  \setcounter{page}{1}
  \noindent
  \begin{center}
    \framebox{
      \vbox{\vspace{2mm}
        \hbox to 6.28in { {{\bf 18.405J/6.841J~Advanced Complexity Theory} \hfill #2} }
        \vspace{4mm}
        \hbox to 6.28in { {\Large \hfill Lecture #1  \hfill} }
        \vspace{2mm}
        \hbox to 6.28in { {\it Lecturer: #3 \hfill Scribe: #4} }
        \vspace{2mm}}}
  \end{center}
  \markboth{Lecture #1: #2}{Lecture #1: #2}
  \vspace*{4mm}
}

\input{epsf}
%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
  \vspace{0.2 in}
  \setlength{\epsfxsize}{#2}
  \centerline{\epsfbox{#4}}
  \begin{center}
    Figure #1:~#3
  \end{center}
}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
\newenvironment{mproof}[1]{{\bf #1}}{\hfill\rule{2mm}{2mm}}

\def\tm{Turing Machine }
\def\ph{{\bf PH}}
\def\pspace{{\bf PSPACE}}
\def\tqbf{{\sf TQBF}}
\def\plog{{\it P}/{\it log}}
\def\exptime{{\bf EXPTIME}}
\def\np{{\bf NP}}
\def\co{{\bf co-}}
\def\zpp{{\bf ZPP}}
\def\rp{{\bf RP}}
\def\E#1{{\rm E}[#1]}
%\def\Pr#1{{\bf Pr}[#1]}
\def\tsat{{\sf 3-SAT}}
\def\npc{{\bf NP}-complete}
\def\p{{\bf P}}
\def\i{\hspace*{5mm}}
\newcounter{lineno}
\setcounter{lineno}{0}
\def\n{\addtocounter{lineno}{1} \hbox to 7mm{\hfill \arabic{lineno}:}\hspace{2mm}}
\def\resetn{\setcounter{lineno}{0}}
\def\tqbfk{\tqbf_k^\exists}
\def\ep{\epsilon}
\def\bpp{{\bf BPP}}
\def\sat{{\sf SAT}}
\def\usat{{\sf USAT}}

\begin{document}
\lecture{8}{February 29, 2000}{Daniel A. Spielman}{Mohammad Mahdian}

In this lecture, we will prove the theorem of Valiant and Vazirani, and
introduce the complexity of counting.

\section{The Valiant-Vazirani Theorem} 
The Valiant-Vazirani Theorem \cite{vv} says that if we can solve \sat\ instances with
unique solutions, then we can solve \sat\ in general (using randomization).
The following is the exact statement of their theorem.

\begin{theorem}
There is a randomized polynomial time Turing machine $M$ that on input $\phi\in$ 3-CNF 
with $n$ variables, $M$ outputs $n+2$ 3-CNFs $\phi_1, \phi_2, \ldots, \phi_{n+2}$
such that 
\begin{itemize}
\item[(i)] if $\phi\in\sat$, then $\Pr[\exists i {\rm\ such\ that\ }\phi_i{\rm\ has\ exactly\ one\ satisfying\ assignment}\,]\ge\frac18$.
\item[(ii)] if $\phi\not\in\sat$, then $\forall i\ \phi_i\not\in\sat$.
\end{itemize}
\end{theorem}

The idea of the proof is to add some additional constraints randomly to the formula $\phi$ to 
get several formulas with fewer satisfying assignments, so that if $\phi$ is 
satisfiable, with high probability at least one of those formulas have exactly
one satisfying assignment.

We need the concept of pairwise independent hash functions that was introduced in 
the problem set 1 (problem 5).

\begin{definition}
A family $\cal H$ of functions from $\{0,1\}^n$ to $\{0,1\}^k$ is {\em pairwise
independent} if
\begin{itemize}
\item for every $x\in \{0,1\}^n$ and $a\in\{0,1\}^k$,  
$$\Pr[h(x)=a]=\frac1{2^k},$$
\item and for every $x,y\in\{0,1\}^n$, $x\neq y$, and $a,b\in\{0,1\}^k$,
$$\Pr[h(x)=a\mid h(y)=b]=\frac1{2^k}.$$
\end{itemize}
\end{definition}

From Problem Set 1, Problem 5, we know that there are families of pairwise independent
hash functions that are easy to compute, i.e., it is possible to construct a circuit
computing a random element of the family in randomized polynomial time. In particular,
the family 
\begin{equation}
\label{hashdef}
{\cal H}_{n,k}=\{h_{M,s}: M \in GF(2)^{n\times k}, s\in GF(2)^k, h_{M,s}(x)=xM+s\}
\end{equation}
is pairwise independent.

Now, assume that we know that the formula $\phi$ has between $2^{k-2}$ and $2^{k-1}$
solutions. We can build a formula $\phi'$ that is satisfied by $\overline{x}$
if and only if
\begin{itemize}
\item $\phi$ is satisfied by $\overline{x}$, and
\item $h(\overline{x})=\overline{0}$, where $h$ is chosen from a pairwise independent
family $\cal H$ at random.
\end{itemize}
We hope that $\phi'$ has just one satisfying assignment. The following lemma
justifies this fact.

\begin{lemma}
\label{lm1}
Let $S$ be a subset of $\{0,1\}^n$ such that $2^{k-2}\le |S|\le 2^{k-1}$, and
$\cal H$ be a pairwise independent family of hash functions from  $\{0,1\}^n$ to
$\{0,1\}^k$. Then
$$\Pr_{h\in{\cal H}}[|S\cap h^{-1}(\overline{0})|=1]\ge \frac18.$$
\end{lemma}
\begin{proof}
We have:
\begin{eqnarray*}
\Pr_{h\in{\cal H}}[|S\cap h^{-1}(\overline{0})|=1]
&=& \Pr_{h\in{\cal H}}[\exists x\in S {\rm\ such\ that\ } (h(x)=\overline{0}\wedge\forall y\in S-\{x\}, h(y)\neq\overline{0})]
\end{eqnarray*}
Since the above events are mutually exclusive, the above probability is equal to:
\begin{eqnarray*}
\Pr_{h\in{\cal H}}[|S\cap h^{-1}(\overline{0})|=1]
&=& \sum_{x\in S}\Pr_{h\in{\cal H}}[h(x)=\overline{0}\wedge\forall y\in S-\{x\}, h(y)\neq\overline{0}]\\
&=& \sum_{x\in S}\Pr_{h\in{\cal H}}[h(x)=\overline{0}]\Pr_{h\in{\cal H}}[\forall y\in S-\{x\}, h(y)\neq\overline{0}\mid h(x)=\overline{0}]\\
&=& \sum_{x\in S}\frac1{2^k}(1-\Pr_{h\in{\cal H}}[\exists y\in S-\{x\}, h(y)=\overline{0}\mid h(x)=\overline{0}])\\
&\ge& \sum_{x\in S}\frac1{2^k}(1-\sum_{y\in S-\{x\}}\Pr_{h\in{\cal H}}[h(y)=\overline{0}\mid h(x)=\overline{0}])\\
&\ge& \sum_{x\in S}\frac1{2^k}(1-\frac{|S|}{2^k})\\
&=& \frac{|S|}{2^k}(1-\frac{|S|}{2^k})\ge \frac14\times\frac12=\frac18.
\end{eqnarray*}
\end{proof}

\begin{lemma}
\label{lm2}
Let ${\cal H}_{n,k}$ be the family defined by Equation \ref{hashdef}. 
For any $h\in{\cal H}_{n,k}$ we can construct in polynomial time a 3-CNF
$\phi_h$ such that
\begin{itemize}
\item[(i)] if $h(\overline{x})=0$, then there is a unique $\overline{y}$ such
that $\phi_h(\overline{x},\overline{y})=0$.
\item[(ii)] if $h(\overline{x})\neq0$, then for every $\overline{y}$, $\phi_h(\overline{x},\overline{y})\neq 0$.
\end{itemize}
\end{lemma}

We don't prove the above lemma, but the proof is easy (It is sufficient to
construct a circuit that computes the function $h$, and then turn the circuit
into a formula).

Now, we are ready to prove the theorem of Valiant and Vazirani.

\begin{mproof}{Proof of Theorem 1: }
For $k=1, \ldots, n$, choose a random hash function $h_k: \{0,1\}^n\mapsto\{0,1\}^k$
from ${\cal H}_{n,k}$ and set 
$\phi_k(\overline{x})=\phi(\overline{x})\wedge\phi_{h_k}(\overline{x},\overline{y})$.
If the number of satisfying assignments to $\phi$ is between $2^{k-2}$ and $2^{k-1}$, then 
by Lemma \ref{lm1} and Lemma \ref{lm2}, $\phi_k$ has just one satisfying assignment with
probability at least $\frac18$.
\end{mproof}

We can formulate this result in terms of the complexity classes. We need the following
definition.

\begin{definition}
For a predicate $Q$, the predicate $\usat_Q$ is defined as follows:
$$\usat_Q(\phi)=\left\{\begin{array}{ll}0 & {\rm\ if\ }\phi\not\in\sat\\
1 & {\rm\ if\ }\phi{\rm\ has\ a\ unique\ satisfying\ assignment}\\
Q(\phi) & {\rm\ otherwise}
\end{array}\right.$$
\end{definition}

The following theorem is a simple corollary of Theorem 1.

\begin{theorem}
If there is a $Q$ such that $\usat_Q\in\rp$, then $\np\subseteq\rp$.
\end{theorem}

\section{The complexity of counting solutions}
In 1979, Valiant asked how hard is it to count the number of solutions.
The above result of Valiant and Vazirani helped to prove Toda's theorem
which says that counting the number of solutions is at least as difficult
as the polynomial hierarchy.

\begin{definition}
$\#\p$ is the class of functions $f:\{0,1\}^n\mapsto N$ for which there is a nondeterministic
polynomial time Turing machine $M$ such that for every word $w$, $M(w)$ has
exactly $f(w)$ accepting paths.
\end{definition}

The language $\#\sat$ that is defined below is the complete problem for $\#\p$
(The proof of this fact, together with the precise definition of $\#\p$-completeness 
will be presented in the next lecture).

\begin{definition}
For every formula $\phi$, $\#\sat(\phi)$ is the number of satisfying assignments
of $\phi$.
\end{definition}

Since \sat\ is an \npc\ problem, it is natural to expect $\#\sat$ to be $\#\p$-complete;
but Valiant proved that it is also possible to get $\#\p$-complete problems out of 
problems that are polynomially solvable:

\begin{theorem}
Let $\#{\sf Matching}$ be the function that computes the number of perfect matchings of
the given graph. Then  $\#{\sf Matching}$ is a $\#\p$-complete problem.
\end{theorem}

Since $\#\p$ is a class of functions, we cannot compare it with the other complexity
classes, which are classes of languages. Therefore, we consider the class $\p^{\#\p}$.
It is clear that \np\ and \co\np\ are both contained in $\p^{\#\p}$. In 1989, Toda
proved the following.

\begin{theorem}
$\ph\subseteq\p^{\#\p}.$
\end{theorem}

\begin{thebibliography}{MM99}
\bibitem{vv}  {\sc L. G. Valiant}, and {\sc V. V. Vazirani}, 
{\it \np\ is as easy as detecting unique
solutions}, Theoretical Computer Science {\bf 47} (1986), no. 1, 85--93. 
\end{thebibliography}

\end{document}