15-451 11/09/00
* More NP-complete problems
* Other complexity classes
===========================================================================
In the discussion below, a "problem" means something like 3-coloring
or network flow, and an "instance" means a specific instance of that
problem --- the graph to color or the network to find a flow on.
NP: problem Q is in NP if there is a verifier V(w,I) that runs in time
poly(|I|) such that:
If "I" is a YES-instance, then there exists w such that V(w,I) = 1.
If "I" is a NO-instance, then for all w, V(w,I) = 0.
E.g., 3-coloring. The instance is the graph and the witness is the
coloring. How about TSP: "Given a graph G and a distance d, does
there exist a tour that visits all nodes and has length <= d?"
(aside: can anyone see how to use a black box that solves this to
actually *find* the tour?)
Note: can actually assume V is linear-time since can pad the instance
with 0's.
Problem Q is NP-complete if:
(1) Q is in NP, and
(2) Any other problem Q' in NP is polynomial-time reducible to Q.
If Q just satisfies (2) then it's called NP-hard.
In some sense, the canonical NP-complete problem is "given a verifier
V (written in some standard programming language), and an instance I,
and a polynomial time-bound B, does there exist w such that V(w,I)
halts in time B and outputs 1?" (We can enforce that B is poly(|I|)
by requiring it to be written in unary.)
Theorem from last time: 3-SAT and Circuit-SAT are NP-complete.
IMPORTANT FACT: now that we have 3-SAT, in order to prove some other
NP problem Q is NP-complete, we just need to show 3-SAT <= Q: if we
could solve Q then we could solve 3-SAT. MAKE SURE YOU UNDERSTAND
THIS - A LOT OF PEOPLE MAKE THE MISTAKE OF DOING IT THE OTHER WAY
AROUND.
MAX-CLIQUE: given a graph G, find the largest clique (set of nodes
s.t. all pairs in the set are neighbors). Decision problem: "Given G
and integer k, is there a clique of size >= k?".
Theorem: Max-Clique is NP-hard.
Proof: reduce 3-SAT to MAX-CLIQUE.
Given a 3-CNF formula F of m clauses over n variables, we construct a
graph as follows. For each clause c of F we create one node for every
assignment to variables in c that satisfies c. E.g., say
F = (x1 OR x2 OR not(x4)) AND (not(x3) OR x4) AND (not(x2) OR not(x3)) AND ...
Then in this case we would create nodes like this:
(x1=0,x2=0,x4=0) (x3=0,x4=0) (x2=0,x3=0) ...
(x1=0,x2=1,x4=0) (x3=0,x4=1) (x2=0,x3=1)
(x1=0,x2=1,x4=1) (x3=1,x4=1) (x2=1,x3=0)
...
Note that there are at most 7m nodes.
Then we put an edge between two nodes if the partial assignments are
consistent. Note: max possible clique size is m. And, if the 3-SaT
problem does have a satisfying assignment, then in fact there IS an
m-clique. Claim is this is true in the other direction too. If the
graph has an m-clique, then there is a satisfying assignment: namely,
just read off the assignment given in the nodes of the clique. So,
Max-Clique is NP-complete too.
Independent Set
===============
An independent set in a graph is a set of nodes no two of which have
an edge. E.g., in a 7-cycle, the largest independent set has size 3.
(E.g, in the graph coloring problem, the set of nodes colored red is
an independent set).
Theorem: Independent set (is there an Indep Set in G of size > k?) is
NP-complete.
Proof: Reduce from clique. Given graph G for clique problem, just
take complement of the graph . Ie. create graph H such that H has
edge (u,v) iff G does NOT have edge (u,v). Then H has an indep set of
size k iff G has a k-clique.
Vertex-Cover
============
A vertex cover in a graph is a set of nodes such that every edge is
incident to at least one. (e.g., look at cut-diamond graph). For
instance, can think of as what rooms to put security guards in a
museum. What we want is the smallest vertex cover.
Decision problem: does there exist a vertex cover of size < k?
Claim: if C is a vertex cover in a graph, then V-C is an independent
set. Also if S is an independent set, then V-S is a vertex cover.
So, to solve "is there an independent set of size > k?" just solve "is
there a vertex cover of size < n-k?". So, Vertex cover is NP-Complete
too.
-------------------------------------------------------------------
More complexity classes: in all these, assume w is a string of
poly(|I|) bits.
NP: Q is in NP if there is a polynomial-time algorithm V(w,I) such that:
If "I" is a YES-instance, then there exists w such that V(w,I) = 1.
If "I" is a NO-instance, then for all w, V(w,I) = 0.
Co-NP: other way around from NP: swap YES and NO.
RP: randomized polynomial time
If "I" is a YES-instance, then for at least half of w, V(w,I) = 1.
If "I" is a NO-instance, then for all w, V(w,I) = 0.
Co-RP: the other way around.
E.g., will see later that primality is in Co-RP: there are efficient
algs such that if N is prime they always output YES, and if N is
composite then with prob >= 1/2 they output NO. Can run many times to
amplify. (If ever see a NO, you know it's not prime. If always see
YES, then probably it's prime)
BPP: two-sided error
If "I" is a YES-instance, then for at least 2/3 of w, V(w,I) = 1.
If "I" is a NO-instance, then for at least 2/3 of w, V(w,I) = 0.
What would a problem that's not even in NP look like? Here's a
problem that's believed to not be in NP: For the n by n version of
chess, does the first player have a winning strategy? (The answer is
not known for the usual 8x8 chess). Might be true --- but even if you
knew it was true, it's not clear how you could give a short proof.