Have a great week everyone and I will see you in February.

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

## Friday, January 24, 2003

### Vacation

### An Efficient Algorithm for Testing whether a Graph is Perfect

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

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

_{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.

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