\documentclass[12pt]{article}

\input{cps130}

\begin{document}

\title{Complexity (23)}
\author{Michael L. Littman}
\date{December 8th, 1998}

\maketitle 

\section{COMPLEXITY}

\subsection{Efficient Algorithms}

\ni We've looked at many different algorithms with varying run times.

\ni Some problems, like topological sort and stable marriage, admitted
low-overhead linear-time (in the size of the input) algorithms.
Others, like solving a system of linear equations and sorting, took
more time.

\ni Many of the problems also had simple exponential-time algorithms,
but we generally felt that these were not the ones we wanted.

\ni These kind of observations have led theoreticians to make a
distinction between polynomial-time and exponential-time algorithms,
with exponential meaning ``bad''.


\subsection{Hard Problems}

\ni We can use the notion of efficient algorithms to categorize
problems: a hard problem is one that has no efficient
(polynomial-time) algorithm.  (This is ``algorithms as a taxonomic
tool!'') 

\ni A natural question to ask is: Are there any hard problems?

\ni Yes.  You can study them (EXP-hard problems) in the complexity
course.  In fact, there are some problems whose answers cannot be
computed!

\ni Amazingly, there is a huge class of important problems whose
status as hard or easy is unknown.  What we do know is that they are
all easy or all hard!

\ni These are the NP-complete problems.  Today will be a quick survey
of why these problems are important in the study of algorithms.  Next
time we'll look at developing algorithms for NP-complete problems.

\subsection{Degrees of Hardness}

\ni Like stones, we can categorize problems by how hard they are:

\ul

\li not computable: halting problem.

\li computable, but not in less than exponential time: succinct
	circuit value, generalized checkers.

\li computable in polynomial time, but not in linear time: sorting
	using only comparisons (Section 9.1).

\li computable in linear time: topological sort.

\el

\ni All of these are tight: can't do any better.  The NP-complete
problems are frustrating because we know how to solve them in
exponential time, but we don't know we {\em can't\/} solve them in
polynomial time.  Big gap!


\section{NP-COMPLETENESS}

\subsection{Decision Problems}

\ni To keep things simple, we will mainly concern ourselves with
decision problems.  These problems only require a single bit output:
``yes'' and ``no''.

\ni How would you solve the following decision problems?

\ul

\li Is this directed graph acyclic?

\ans{DFS, look for visit to a gray node.  Linear time.}

\li Is there a spanning tree of this undirected graph with total
weight less than $w$?

\ans{MST, compare resulting value to $w$.  Polynomial time.}

\li Does this bipartite graph have a perfect (all nodes matched)
matching?

\ans{Find maximum matching and see if all nodes are matched.
Polynomial time.}

\li Does the pattern $p$ appear as a substring in text $t$?

\ans{String search.  Polynomial time.}

\el

\subsection{Decision to Optimization}

\ni In the previous examples, we find an optimal answer to solve the
decision problem.

\ni How would you use a decision problem to solve the optimization
problem?

\ni For example, imagine we have a subroutine for telling us whether
there is a spanning tree of a graph that has weight less than $w$.
How can we find the minimum weight efficiently?

\ans{Binary search.}

\ni Now, how do we find the MST?

\ans{Self reducibility.  Once we know the size of the MST, we can drop
out an edge and see if we're still ok.  Drop the edges that are ok to
drop and keep the others.  When we're through, we'll have the MST!}


\subsection{P}

\ni P is the set of decision problems that can be solved in worst-case
polynomial time:

\ul

\li If the input is of size $n$, the running time must be $O(n^k)$.

\li Note that $k$ can depend on the problem class, but not the
particular instance.

\el

\ni All the decision problems mentioned above are in P.



\subsection{Nice Puzzle}

\ni The class NP (meaning non-deterministic polynomial time) is the
set of problems that might appear in a puzzle magazine: ``Nice
puzzle.''

\ni What makes these problems special is that they might be hard to
solve, but a short answer can always be printed in the back, and it is
easy to see that the answer is correct once you see it.

\ni Example...  Does matrix $A$ have an $LU$ decomposition?

\ni No guarantee if answer is ``no''.

\subsection{NP}

\ni Technically speaking:

\ul

\li A problem is in NP if it has a short accepting certificate.

\li An {\em accepting certificate\/} is something that we can use to
quickly show that the answer is ``yes'' (if it is yes).

\li {\em Quickly\/} means in polynomial time.

\li {\em Short\/} means polynomial size.

\el

\ni This means that all problems in P are in NP (since we don't even
need a certificate to quickly show the answer is ``yes'').

\ni But other problems in NP may not be in P.  Given an integer $x$,
is it composite?  How do we know this is in NP?

\ans{Can prove it is by writing down its factors.  Can check in
polynomial time using multiplication.}

\subsection{Good Guessing}

\ni Another way of thinking of NP is it is the set of problems that
can solved efficiently by a really good guesser.

\ni The guesser essentially picks the accepting certificate out of the
air (Non-deterministic Polynomial time).  It can then convince itself
that it is correct using a polynomial time algorithm.  (Like a
right-brain, left-brain sort of thing.)

\ni Clearly this isn't a practically useful characterization: how
could we build such a machine?

\ni (Although, researchers have been recently entranced by the idea
that superposition properties of quantum mechanics can simultaneously
try out all guesses quickly.  But, I don't think this panned out.)

\subsection{Exponential Upperbound}

\ni Another useful property of the class NP is that all NP problems
can be solved in exponential time (EXP).

\ni This is because we can always list out all short certificates in
exponential time and check all $O(2^{n^k})$ of them.

\ni Thus, P is in NP, and NP is in EXP.  Although we know that P is
not equal to EXP, it is possible that NP = P, or EXP, or neither.
Frustrating!


\subsection{NP-hardness}

\ni As we will see, some problems are at least as hard to solve as any
problem in NP.  We call such problems {\em NP-hard\/}.

\ni How might we argue that problem $X$ is at least as hard (to within
a polynomial factor) as problem $Y$?  

\ans{Show we can use an algorithm for $X$ to solve $Y$.}

\ni If $X$ is at least as hard as $Y$, how would we expect an
algorithm that is able to solve $X$ to behave?

\ans{Shouldn't take any longer to solve $Y$.  Like a shortest path
argument.}

\subsection{Reducibility}

\ni The idea of reducibility is really just a matter of using a
solution to one problem as a subroutine in solving another.

\ni We say problem $Y$ is (polynomial) reducible to $X$ if we can
solve $Y$ using a polynomial number of calls to an algorithm for $X$.

\ni This implies that $Y$ is as easy as $X$ ($X$ is at least as hard
as $Y$).

\ni We used this idea when we talked about least squares and solving
linear equations: we can reduce least squares to solving linear
equations very directly.

\subsection{NP-Completeness}

\ni For a problem $X$ to be NP-complete, it needs to satisfy two
properties:

\ul

\li $X$ is in NP (short accepting certificate).

\li $X$ is NP-hard (an NP-hard problem can be reduced to it).

\el

\ni The NP-complete problems are the hardest problems in NP.  If even
one of them can be solved in polynomial time, then they {\em all\/}
can.

\ni Books of such problems exist...

\section{NP-COMPLETE PROBLEMS}

\subsection{Set Covering}

\ni We want to make a small committee to look into global warming, but
we want to make sure all of the following 7 groups are represented:
Women, Homosexuals, Jews, African Americans, Tall people, Native
Americans, Republicans.

\begin{tabular}{lc}
Mick &   F F F F F T F\\
Harvey & F T T F T F T\\
Wilt &   F F F F T T F\\
Sue &    T T T F F T F\\
Barney & F F F F T F F\\
Myrna &  T F T F F F T\\
Tiffany &T F F T T T F
\end{tabular}

\ni Minimal set cover: No one redundant.  How solve this efficiently?

\ans{One algorithm would be: Start with the full set of people.  While
there is a redundant person, remove him/her.  When we're done, we
cover the same set but no one can be removed.}

\ni Minimum set cover: Smallest possible committee.  How solve this
efficiently?

\ans{Ah, there's the rub.}

% minimum: Tiff and Harvey
% minimal: gals

\subsection{Decision-Problem Version}

\ni The decision-problem version is ``Is there a set cover of size $k$
or smaller?''

\ni How could you use an algorithm for this to find the minimum
set cover?  Assume $n$ people.

\ul

\li Binary search: $\log n$ queries.

\li Self-reduction: $n$ queries to see who is needed.

\el

\ni Try it.

\subsection{Hard Problem}

\ni There is no known polynomial-time algorithm for set cover.

\ni Even more striking, the problem is NP-complete.  This means that,
unless P = NP, there is no polynomial-time algorithm for set cover.

\ni We'll prove this shortly.  NP-complete = in NP + NP-hard.  Argue
that it is in NP.  We'll do hardness shortly.

\ans{If I give you a possible cover, we can check that it has no more
than $k$ people and covers the set.}

\subsection{SAT}

\ni To prove a problem is NP-hard, it helps to have other NP-hardness
problems around to reduce to it.

\ni Cook proved the first NP-hard problem.

\ni 3CNF-SAT (sometimes just SAT) is a popular version of the problem:

\ul

\li Given a Boolean formula in conjunctive normal form with at most 3
variables per clause, is there an assignments to its variables that
makes the formula true?

\el

\ni Example...

\ni SAT is in NP: assignment is the certificate.

\ni SAT is NP-hard essentially because we can ``build'' a special
guessing computer out of logic gates.  We can write any problem in NP
as a program for this computer.

\ni This computer has some non-deterministic components that express
an accepting certificate.  The formula will be satisfiable only if the
computer will print ``yes'' for some certificate.

\subsection{Hardness of Set Cover}

\ni Now we have one NP-complete problem.

\ni Can prove set cover is no easier by showing how an algorithm for
set cover could be used to solve SAT.

\ni How can we determine satisfiabilty with a polynomial number of
calls to an algorithm for set cover?

\ul

\li First, augment the formula with a clause for all $n$ variables
(contains positive and negative literal).

\li Now, each clause becomes something to be covered (a ``minority
group'').

\li Each literal (positive or negative variable) becomes a potential
committee member that ``covers'' the clauses that it appears in.

\li Problem has a size $n$ cover if and only if formula is satisfiable.

\el

\ni Example...

\subsection{Fine Points}

\ul

\li Can't have a set cover of size smaller than $n$ because of the
``variable'' clauses.  

\li Further, a size $n$ cover will not include a positive and negative
literal for the same variable.  Therefore, it corresponds to an
assignment.

\li A size $n$ cover will have a true variable in every clause,
therefore it will correspond to a satisfying assignment.

\el

\ni Amazing how SAT can hide itself in other problems: set covering is
just SAT in disguise!


\subsection{Graph Coloring}

\ni We'd like to take a map consisting of a set of non-overlapping
regions and ``color'' it (assign a color to each region) so that no
two contiguous regions have the same color.  Want to minimize the
number of colors.

\ni Important in scheduling problems.

\ni What's the natural decision problem?

\ans{$k$-colorability.}

\subsection{Solving 3-colorability}

\ni Algorithm for solving it?

\ni In NP?

\ans{Sure... show me the colors.}

\ni How use an algorithm for 3-colorability to solve SAT?

\subsection{Reduction}

\ni Not too bad.

\ul

\li Triangle: true, false, red.

\li Each literal becomes a node with an edge to ``red.''  Its color
(which can only be ``true'' or ``false'') represents its assignment.
A literal and its complement are connected by an edge to assure that
they don't get the same color.

\li Each clause becomes a set of 5 nodes (widget): insures that all 3
literals are not ``false.''  (Proof by exhaustion.)

\el

\begin{verbatim}
x-o
  |\
y-o-o-o
      |\
z-----o-true

 x
 |\
~x-red
\end{verbatim}

\ni Graph has a 3 coloring if and only if formula has a satisfying
assignment.

\subsection{Colorability Complexity for Planar Graphs}

\ni A planar graph is one that you can draw on paper without edge
crossings.  Example: $K_{3,2}$ vs. $K_{3,3}$.

\ni Complexity of determining $k$-colorability for planar graphs as a
function of $k$:

\ul

\li 1: $O(1)$ (can't do it if there are any edges at all).

\li 2: $O(|V|+|E|)$ (BFS!).

\li 3: NP-complete (special widget to take general reduction and
eliminate edge crossings).

\li 4: $O(1)$ (famous 4-color map theorem, always ``yes'').

\el

\ni The number 3 comes up in many NP-complete problems!


\section{PRACTICE PROBLEMS}

\ul

\li Explain how to use a solution to the bipartite matching decision
problem to find a maximum bipartite matching of a graph.  Hint: First
use a binary search to find the size of the maximum matching, then use
self-reducibility to find the set of edges that attains this value.

% \li CLR Exercise 36.4-6 (pg. 946).

\li CLR Exercise 36.4-7 (pg. 946).

\li CLR Exercise 36.5-2 (pg. 960).

\el


\end{document}

