Computational Complexity

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₀, v₁, the abstractor "λ", the separator "." and parentheses "(" and ")". The set of lambda terms is the smallest set such that

1. Every variable is a lambda term.
2. If M is a lambda term then (λx.M) is a lambda term.
3. 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² in E=mc² is different than Pythagoras' c² in a²+b²=c²." And all this time I thought E=m(a²+b²).

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.

1. Every configuration has exactly one state, head location and each tape cell has one element.
2. conf₀ is the initial configuration.
3. conf_m is accepting.
4. 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₁...x_n, b the blank character and state 0 the initial state. We have the following single variable clauses, q₀₀
h₀₁
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 []   

Archives