np_complete.tex

\chapter{NP-Complete}

The complexity class known as \emph{NP-Complete} is a special subset
of $NP$, such that any problem in \emph{NP} can be translated to a
problem in \emph{NP-Complete} in polynomial time.

\section{CIRCUIT-SAT}

Given a boolean circuit, is it possible to provide a set of inputs
that cause the output to be \emph{True}?

In 1971, Cook proved that \emph{CIRCUIT-SAT} is \emph{NP-Complete}.
The proof is beyond the scope of these notes.  Cook showed that all
operations of a polynomial-sized Turing machine can be performed in
polynomial time using an instance of this problem.  In other words,
Cook showed that a Turing machine can be implemented using circuits
(surprise!!).

\section{Reduction}

Given at least one \emph{NP-Complete} problem, we can prove any other
problem $L$ is \emph{NP-Complete} by showing that $L \in NP$ and that
given an instance $x$ of a proven \emph{NP-Complete} problem we can
translate $x$ to an instance of $L$ in polynomial time, such that by
solving our generated instance of $L$, we can solve $x$.

The steps to do this are:

\begin{enumerate}
\item Show $L \in NP$.  We do this by first showing that the
  certificate for $L$ is polynomial with respect to the input, and
  that a certificate for $L$ can be verified in polynomial time.

\item Select a known \emph{NP-Complete} $L'$, ideally one that is
  similar to $L$.

\item Describe a polynomial time algorithm that maps any instance $x
  \in L'$ to an instance $f(x) \in L$.

\item Show that we can solve $x \in L'$ if and only if we can solve
  $f(x) \in L$.
\end{enumerate}

\section{SAT}

Given a boolean formula, are there values of the variables that cause
the formula to be \emph{True}?

First let us show that $SAT \in NP$ by using the truth values as a
certificate, which is clearly polynomial in size because it is
necessarily a subset of the input.  To verify, we evaluate the formula
given the truth values and return the output.

Next, we select \emph{CIRCUIT-SAT} from which to reduce to this
problem.

Then given an instance of \emph{CIRCUIT-SAT}, we transform the circuit
to a boolean formula such that the circuit is satisfiable if and only
if the formula is satisfiable.  We can do this easily by mapping gates
to boolean operators.

Since the instances of each problem are equivalent, it should be easy
to see that one is satisfiable if and only if the other is.

\section{3CNF-SAT}

Is a given boolean formula in \emph{3CNF} form satisfiable?  A boolean
formula is said to be in \emph{3CNF} form if there are no more than
$3$ variables in each clause, and within a clause there are only
\emph{OR} operators and between clauses there are only \emph{AND}
operators.

By the same proof as \emph{SAT} above, $3CNF-SAT \in NP$.

We reduce from \emph{SAT}.  Given an instance of \emph{SAT}, we use
equivalences to reduce all boolean operators to \emph{AND}, \emph{OR},
and \emph{NOT}.  Then we use DeMorgan's law to put the formula into
\emph{3CNF} form.

Since the instances of each problem are equivalent, it should be easy
to see that one is satisfiable if and only if the other is.

\section{CLIQUE}

Given a simple, undirected graph $G$, find a \emph{complete} subgraph
of $G$ of at least size $k$.

Let the certificate be the set of vertices on which there is a
complete subgraph.  Since this is necessarily a subset of the input
vertices, it must be of polynomial size.  We can verify the set of
vertices are complete by checking that every pair of vertices $i,j$
where $i \neq j$ are adjacent, and we can easily check if the set is
of size $k$ by counting them.

We reduce from \emph{3CNF-SAT}.  Given an instance $\Phi$ of \emph{3CNF-SAT}
with $k$ clauses, we would like to construct an instance of
\emph{CLIQUE}.  Our graph has $3k$ vertices, one for each variable in
each clause.  Clause $r$ has vertices $v^r_1,v^r_2,v^r_3$.  We put an
edge between $v^r_i$ and $v^s_j$ if and only if:

\begin{itemize}
\item $r \neq s$
\item their literals are consistent
\end{itemize}

\begin{lemma}
  If $\Phi$ is satisfiable, then $G$ must contain a clique of size $k$.
\end{lemma}

\begin{proof}
  Assume $\Phi$ is satisfiable, which is to say that $\Phi$ has a
  satisfying truth assignment.  We select the vertices corresponding
  to that truth assignment.  Since this truth assignment satisfies
  $\Phi$, there must exist one selected vertex in each box.  Each of
  these is connected to every vertex in a different box, therefore
  there exists a clique in $G$.
\end{proof}

\begin{lemma}
  If $G$ contains a clique of size $k$, then $\Phi$ is satisfiable.
\end{lemma}

\begin{proof}
  Assume $G$ contains a clique of size $k$.  One vertex of the clique
  must be in each box.  Assign all variables corresponding to the
  vertices of the clique to be true.  This must be a satisfying
  assignment because at least one true variable exists in each clause,
  and there are no inconsistent truth values.
\end{proof}

\begin{theorem}
  $\Phi$ is satisfiable if and only if $G$ contains a clique of size $k$.
\end{theorem}

\begin{proof}
  This follows from the above lemmas.
\end{proof}

\section{VERTEX-COVER}

Given a graph $G=(V,E)$, does there exist a set of vertices $V'$ of
size at most $k$ such that every edge in $E$ is incident to one vertex
in $V'$?

Let the certificate be the set of vertices $V'$.  This is a subset of
$V$, so it is polynomial with respect to the input.  We can verify
that $V'$ is of size at most $k$ by counting the vertices in $V'$.  We
can verify that the vertices in $V'$ form a vertex cover of $G$ by
checking that every edge in $E$ is incident to at least one vertex in
$V'$ in polynomial time.

We reduce from \emph{Clique}.  Let $\overline G = (V, \overline E)$ be
the complement of the graph $G$, where $\overline E = \{ (u,v) | (u,v)
\not \in E \}$.

\begin{lemma}
  $\overline G$ has a vertex cover of size $|V| - k$ if $G$ has a
  clique of size $k$.
\end{lemma}

\begin{proof}
  Assume $G$ has a clique $V'$ of size $k$.  $V \ V'$ is a vertex
  cover of $G$.  Let $(u,v) \in \overline E$, $u$ and $v$ are not both
  in $V'$.  Either $u$ or $v$ is in $V \ V'$.
\end{proof}

\begin{lemma}
  $G$ has a clique of size $k$ if $\overline G$ has a vertex cover of
  size $|V| - k$.
\end{lemma}

\begin{proof}
  Assume $\overline G$ has a vertex cover $V'$ of size $|V| - k$.  For
  all edges $(u,v) \in \overline E$, either $u$ is in $V'$ or $v$ is
  in $V'$.  For all vertices $u$,$v$ and $u \neq v$ then if neither
  $u$ nor $v$ is in $V'$ then $(u,v) \in E$.
\end{proof}

\begin{theorem}
  $G$ has a clique of size $k$ if and only if $\overline G$ has a
  vertex cover of size $|V| - k$.
\end{theorem}

\begin{proof}
  This follows from the preceding lemmas.
\end{proof}

\section{HAM-CYCLE}

Given a graph $G=(V,E)$, does there exist a simple cycle of at least
size $k$ that contains every vertex in $V$?

The proof that this is \emph{NP-Complete} is beyond the scope of these
notes, and not terribly interesting.

\section{TSP}

Given $G=(V,E)$ which is the complete graph on $n$ vertices and each
edge $(u,v)$ has a cost $c(u,v)$, does $G$ have a cycle which visits
each vertex (except the start) exactly once with total cost of at most
$k$?  We call such a cycle a \emph{TSP-tour}

Let the certificate be a permutation of the vertices which is
$\BigOh{|V| + 1}$, so polynomial in size.  We can verify a certificate
by summing the edges between each of the subsequent vertices in the
permutation and checking that the sum is at most $k$.

We reduce from \emph{HAM-CYCLE}.  Given a graph $G=(V,E)$ on which we
would like to solve \emph{HAM-CYCLE}, we create $G'=(V,E')$ where $E'
= \{ (u,v) | u,v \in V, u \neq v \}$.  And we create a cost function:

\begin{math}
  c(u,v) = \left\{ 
    \begin{array}{l l}
      0 & \text{if } (u,v) \in E \\
      1 & \text{if } (u,v) \not \in E \\
    \end{array} \right.
\end{math}

It should be easy to see that $G$ has a \emph{HAM-CYCLE} if and only
if $G'$ has a \emph{TSP-tour} of $k \leq 0$.

\section{SUBSET-SUM}

Given a set $S$ of integers, does there exist a subset whose sum is
exactly $k$?

Let the certificate be the subset of $S$, which is clearly polynomial
with respect to the input.  We can verify the subset by calculating
the sum and comparing it to $k$ in polynomial time.

We reduce from \emph{3CNF-SAT}.  Given a \emph{3CNF} formula over
variables $x_1, ..., x_n$, and clauses $c_1,...,c_k$, we assume
without loss of generality that all variables appear in at least one
clause and no clause contains a variable and its negation.

We create two tables the columns of which are labeled with the
variables in order then the clauses in order.  

The first table's rows are labeled by each variable followed by its
negation.  The value in the table at a given row and column is 1
either if the column is labeled with a variable and the row is labeled
with either that variable or its negation; or the column is labeled
with a clause and that clause contains exactly that variable (or
exactly that negated variable).

The second table's rows are labeled with $s_1,s_1'$ for $c_1$, and
similarly for $c_2,...,c_k$.  The value in the row labeled $s_i$ is 1
in the column labeled $c_i$, and the value in the row labeled $s_i'$
is 2 in the column labeled $c_i$, and 0 otherwise.

The rows of these tables give the digits of numbers in some base
(let's say 10), and the target sum is the number with $n$ 1's followed
by $k$ 4's.

It should be easy to see that we can find a subset which is exactly
the target if and only if the \emph{3CNF} formula is satisfiable.

\section{0/1-Integer Programming}

Beyond the scope of these notes, but interesting.

\section{3-COLOR}

Given a graph $G=(V,E)$, can we label the vertices of a graph using 3
colors such that no adjacent vertices have the same color?

Beyond the scope of these notes, but interesting.