Friday, January 24, 2003
Next week I will go away on vacation. When I go on a real vacation I go cold turkey on the Internet. No new
posts or responses to comments or email until I return.
Have a great week everyone and I will see you in February.
An Efficient Algorithm for Testing whether a Graph is Perfect
Last year we saw the resolution of the Strong Perfect Graph
Conjecture, a major result in graph
theory. The conjecture stated that a graph is perfect if
and only if it does not contain an induced
subgraph H such that H or its complement is an odd cycle of length
at least five. Chudnovsky, Robertson, Seymour, and Thomas proved the
conjecture (now called the Strong Perfect Graph Theorem) last spring.
Vašek Chvátal has a
page describing this result.
Why am I mentioning this result here? The problem of testing whether a
graph is perfect in polynomial-time remained open even after this
theorem as neither characterization gives an obvious
algorithm. I just saw the the
abstract of a talk that Paul Seymour will give at the Institute of
Advanced Study next week. There he claims he and Chudnovsky have found
a polynomial-time algorithm for testing whether a graph is perfect. I
cannot find more about the algorithm on the web and I will miss the
talk at the institute. I will post more information about this
exciting new development when I have more details.
Thursday, January 23, 2003
The Lambda Calculus, Part 1
One cannot celebrate Alonzo Church, part of our Celebration
of Geniuses without talking about his creation, the Lambda Calculus, a
way to describe functions and functional evaluation with a very simple
description and incredible power.
As an example, consider the square function, square(x)=x*x. Suppose we
don't care about the name and just want to talk about the function in
the abstract. The lambda calculus gives us the syntax for such
discussions. We express the square function as
This is a function that takes one argument and returns its square. For
λx.x*x(5) = 25
Also note that the use of x is not important. The following is also
the square function.
So now let us formally define the syntax of
the Lambda Calculus. The alphabet consists of an infinite list of
variables v0, v1, the abstractor
"λ", the separator "." and parentheses
"(" and ")". The set of lambda terms is the
smallest set such that
We will sometimes leave off parentheses when the meaning is clear.
Examples of lambda terms are xx, λx.xx,
- Every variable is a lambda term.
- If M is a lambda term then (λx.M) is a lambda term.
- If M and N are lambda terms then MN is a lambda term.
Free variables are those not closed off by a λ. For example in
λy.xy the variable x is free and y is bound.
We use the notation M[x:=E] means replace every occurrence in the
lambda term M of the free variable x by the lambda term E. There should not
be any free variables in E that are bound in M as this could cause
There are two basic operations:
(renaming variables formally called α-conversion)
λx.M to λy.M[x:=y] where y does not occur in M
(function evaluation formally called β-reduction)
λx.M(E) to M[x:=E]
Church and Rossner have shown that if you have a complicated
lambda-term it does not matter what order the
β-reduction operations are applied.
What can you do with just these simple operations? You get the same
power as Turing machines! It's instructive to see this connection and
we'll go over the proof over several posts in the future.
Breaking Real-World Locks with Cryptography
Just in case you thought computer scientists only deal with computers, here is a New York Times article describing how AT&T researcher Matt Blaze using tools of cryptography to open locks that use a master key. Blaze has been in the news often in the past, usually for breaking various cryptographic schemes. It is neat to see the same ideas used to break mechanical locks.
Tuesday, January 21, 2003
The Why Me? File
Last night I (and forty other complexity theorists) received by email
an anonymous paper entitled "NP = coNP". After a quick scan it was
clear there was not much in the paper, so it will just become another
entry in my Why Me? file.
Each year for the past dozen years, I receive various papers by people
I've never heard of claiming great results in computer science or
mathematics. I started the Why Me? file to collect these various
manuscripts. In those early ancient days I received papers by postal
mail, now I always get them electronically. All of the papers have
been incorrect ranging from subtle errors to papers that just don't
understand the question. What motivates these people? A chance for
glory I suppose.
Most of the papers I get are variants on the P versus NP question,
though a surprising number claim to have counterexamples to Cantor's
Theorem that there are more reals than integers. As one author put it,
Theorem is true if you consider only integers with a finite
number of digits." My favorite is one of the earliest letters I got
from a person who believes he deserves the first Noble (sic) prize in
mathematics. "We have conclusively shown that Einstein's c2
in E=mc2 is different than Pythagoras' c2 in
a2+b2=c2." And all this time I
I never spend more than a few seconds on any of these papers and I
certainly never respond which is only asking for trouble. If there is
any chance of it being correct, I can wait until someone else finds
Here is my suggestion to any of you who think you have the
theorem of the century: Send it to a grad student with an opening line
like "Because you are an expert in complexity...". They'll happily
read your paper and tell you the errors of your ways. If by some fluke
the result is correct the student will spread it around to the
community and you'll get your fifteen minutes of fame.
Monday, January 20, 2003
Foundations of Complexity
Lesson 14: CNF-SAT is NP-complete
Prevous Lesson |
We will show that CNF-SAT
Let A be a language in NP accepted by a nondeterministic Turing
machine M. Fix an input x. We will create a 3CNF formula φ that
will be satisfiable if and only if there is a proper
tableau for M and x.
Let m be the running time of M on x. m is bounded by a polynomial in
|x| since A is in NP. m is also a bound on the size of the
configurations of M(x).
We will create a set of Boolean variables to describe a tableau and a
set of clauses that will all be true if and only if the tableau is
proper. The variables are as follows.
We create four clause groups to check that the tableau is proper.
- qij: true if confi is in state j.
- hik: true if the head in confi is at
- tikr: true if the tape cell in location k of
confi has element r.
1. We will just do this for states. The others are
similar. Suppose we have u possible states.
- Every configuration has exactly one state, head location and each
tape cell has one element.
- conf0 is the initial configuration.
- confm is accepting.
- For each i≤m, confi+1 follows from confi
in one step.
Each configuration in at least one state. For each i we have
qi0 OR qi1 OR ... OR qiu
Each configuration in at most one state. For each i and possible
states v and w, v≠w
(NOT qiv) OR (NOT qiw)
2. Let x=x1...xn, b the blank character and
state 0 the initial state. We have the following single
t0ixi for i≤n
t0ib for i>n
3. Let a be the accept state. We need only one single variable clause.
4. We need two parts. First if the head is not over a tape location
then it should not change.
((NOT hik) AND tikr)→ ti(k+1)r
Now this doesn't look like an OR of literals. We now apply the facts
that P→Q is the same as (NOT P) OR Q and NOT(R AND S) is equivalent to
(NOT R) OR (NOT S) to get
hik OR (NOT tikr) OR t(i+1)kr
At this point none of the formula has been dependent on the machine M.
Our last set of clauses will take care of this. Recall the program of a
Turing machine is a mapping from current state and tape character
under the head to a new state, a possibly new character under the head
and a movement of the tape head one space right or left. A
nondeterministic machine may allow for several of these
possibilities. We add clauses to prevent the wrong operations.
Suppose that the following is NOT a legitimate transition of M: In
state j and tape symbol r, will write s, move left and go to state
v. We prevent this possibility with the following set of clauses (for
all appropriate i and k).
(qij AND hik AND tikr)→
NOT(t(i+1)ks AND hi(k-1) AND q(i+1)v)
which is equivalent to
(NOT qij) OR (NOT hik) OR (NOT tikr)
OR (NOT t(i+1)ks) OR (NOT hi(k-1))
OR (NOT q(i+1)v)
We do this for every possible illegitimate transition. Finally we just
need to make sure the head must go one square right or left in each
(NOT hik) OR h(i+1)(k-1) OR h(i+1)(k+1)
Just to note in the above formula we need special care to
handle the boundary conditions (where k is 1 or m) but this is