### Friday, January 24, 2003

**Vacation**

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.

1:16 PM
#
Comments
[]

**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
web
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.

10:25 AM
#
Comments
[]

### 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

λx.x*x
This is a function that takes one argument and returns its square. For
example
λx.x*x(5) = 25
Also note that the use of x is not important. The following is also
the square function.
λy.y*y
So now let us formally define the syntax of
the Lambda Calculus. The alphabet consists of an infinite list of
variables v_{0}, v_{1}, the abstractor
"λ", the separator "." and parentheses
"(" and ")". The set of lambda terms is the
smallest set such that
- 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.

We will sometimes leave off parentheses when the meaning is clear.
Examples of lambda terms are xx, λx.xx,
λx.λy.yx.

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
confusion.

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.

10:31 AM
#
Comments
[]

**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.
6:24 AM
#
Comments
[]

### 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,
"Sure, Cantor's
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 c^{2}
in E=mc^{2} is different than Pythagoras' c^{2} in
a^{2}+b^{2}=c^{2}." And all this time I
thought E=m(a^{2}+b^{2}).

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
the bug.

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.

11:08 AM
#
Comments
[]

### Monday, January 20, 2003

**Foundations of Complexity **

Lesson 14: CNF-SAT is NP-complete

Prevous Lesson |
Next Lesson
We will show that CNF-SAT
is NP-complete.
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.

- q
_{ij}: true if conf_{i} is in state j.
- h
_{ik}: true if the head in conf_{i} is at
location k.
- t
_{ikr}: true if the tape cell in location k of
conf_{i} has element r.

We create four clause groups to check that the tableau is proper.
- Every configuration has exactly one state, head location and each
tape cell has one element.
- conf
_{0} is the initial configuration.
- conf
_{m} is accepting.
- For each i≤m, conf
_{i+1} follows from conf_{i}
in one step.

1. We will just do this for states. The others are
similar. Suppose we have u possible states.

Each configuration in at least one state. For each i we have
q_{i0} OR q_{i1} OR ... OR q_{iu}
Each configuration in at most one state. For each i and possible
states v and w, v≠w
(NOT q_{iv}) OR (NOT q_{iw})
2. Let x=x_{1}...x_{n}, b the blank character and
state 0 the initial state. We have the following single
variable clauses,
q_{00}

h_{01}

t_{0ixi} for i≤n

t_{0ib} for i>n
3. Let a be the accept state. We need only one single variable clause.
q_{ma}
4. We need two parts. First if the head is not over a tape location
then it should not change.
((NOT h_{ik}) AND t_{ikr})→ t_{i(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
h_{ik} OR (NOT t_{ikr}) 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).

(q_{ij} AND h_{ik} AND t_{ikr})→
NOT(t_{(i+1)ks} AND h_{i(k-1)} AND q_{(i+1)v})
which is equivalent to
(NOT q_{ij}) OR (NOT h_{ik}) OR (NOT t_{ikr})
OR (NOT t_{(i+1)ks}) OR (NOT h_{i(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
turn.
(NOT h_{ik}) 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
straightforward.
2:41 PM
#
Comments
[]