Complexity Class of the Week: The Permanent

Previous CCW

Let A={a_ij} be an n×n matrix over the integers. The determinant of the A is defined as

Det(A)=Σ_σ(-1)^|σ| a_1σ(1)a_2σ(2)...a_nσ(n) where σ ranges over all permutations on n elements and |σ| is the number of 2-cycles one has to apply to σ to get back the identity.

The determinant is computable efficiently using Gaussian Elimination and taking the product of the diagonal.

The permanent has a similar definition without the -1 term. We define the permanent of A by

Perm(A)=Σ_σ a_1σ(1)a_2σ(2)...a_nσ(n) Suppose G is a bipartite graph and let a_ij be 1 if there is an edge from the ith node on the left to the jth node on the right and 0 otherwise. Then Perm(A) is the number of perfect matchings in G.

Unlike the determinant the permanent seems quite hard to compute. In 1979, Valiant showed that the permanent is #P-complete, i.e., computing the permanent is as hard as counting the number of satisfying assignments of a Boolean formula. The hardness of the permanent became more clear after Toda's Theorem showing that every language in the polynomial-time hierarchy is reducible to a #P problem and then the permanent.

The permanent is difficult to compute even if all the entries are 0 and 1. However determining whether the permanent is even or odd is easy since Perm(A) = Det(A) mod 2.

Since we can't likely compute the permanent exactly, can we approximate it? The big breakthrough came a few years ago in a paper by Jerrum, Sinclair and Vigoda showing how to approximate the permanent if the entries are not negative.

Theory A and Theory B

Four speakers are chosen for the NVTI Theory Day along two axis: In and out of the Netherlands, and Theory A and Theory B. For example I was the non-Dutch Theory A speaker. But what is Theory A and B?

In 1994, the Handbook of Theoretical Computer Science was published as a two volume set each containing many survey articles that have for the most part stood the test of time. From the backcover: Volume A [Algorithms and Complexity] covers models of computation, complexity theory, data structure and efficient computation. Volume B [Formal Models and Semantics] presents material on automata and rewriting systems, foundations of programming languages, logics for program specification and verification and modeling of advanced information processing.

Over the years, Theory A and Theory B have come to represent the areas discussed in the corresponding volumes. In the US the term theoretical computer science covers areas mostly in Theory A. For example STOC and FOCS, the major US theory conferences, cover very little in Theory B. This is not to say Theory B is not done in this country; it is just labelled as logic or programming languages.

Outside the US there is a broader view of what is theory. The European ICALP conference covers both areas and has two submission tracks A and B that again correspond to Theory A and B.

Some countries, like Britain and France, focuses mostly on Theory B. Other countries, like the Netherlands and Germany have many groups in both areas.

Some Europeans are upset that their research is not considered theory by the Americans. Too bad.

Talk Posted

I posted the slides of my talk, "Church, Kolmogorov and von Neumann: Their Legacy Lives in Complexity" that I presented at the Dutch Theory Day last week, for those that are interested.

Rush Hour

John Tromp at CWI has been telling me about some work he is doing on the Rush Hour problem. Rush Hour is a puzzle where you have to remove a car stuck in gridlock. A nice description of the problem is presented in a Science News article.

The general problem is PSPACE complete shown by Eric Baum and Gary Flake when they were at NEC. Tromp tells me that he has shown the problem is still PSPACE-complete when the cars are 2x1. Oddly enough the 1x1 case is the hardest to analyze and its complexity remains wide open.

Also check out Tromp's Rush Hour mazes.

Cardinality Theorem for Regular Languages?

Till Tantau told me an interesting open question at STACS. Kummer proved the following Cardinality Theorem for the recursive sets: Fix a constant k and set A. If there is a recursive function f such that for all x₁,...,x_k, f(x₁,...,x_k) is a number between 0 and k that is not |{x₁,...,x_k}∩A| then A is recursive. The same is not true for polynomial time but is open for regular languages. Details and some partial results in Tantau's paper.

Howdy from Berlin

I'm writing from the STACS conference, one of my favorite European conferences. Next week I'll be in Holland visiting CWI and talking at the NVTI Theory Day.

Far less Americans than usual this year. While European travel is definitely down (my plane was quite empty), scientists are usually not deterred by political events. More likely is the drop in grant money forcing researchers to be more picky in their choice of conferences. This year the Complexity Conference is in Europe as well.

Also far less French than usual, STACS being a joint French-German conference. I have no explanation for this.

This is not a science item but interesting nevertheless: I had to rebook my flight back; the US government needed the plane to "fight terrorism", most likely to ferry troops to the Gulf.

There have been some interesting talks at the conference. I'll try to mention some of them when I get a chance.

A Zero-One Law for RP

Russell Impagliazzo and Phillipe Moser have an upcoming Complexity paper entitled A Zero-One Law for RP. What does that mean?

Jack Lutz defined a notion of resource-bounded measure to find the relative size of complexity classes within exponential time. He has many surveys and research papers available on this interesting topic. Whether NP has measure zero in EXP is the most exciting open question in this area.

Dieter van Melkebeek noted that the Impagliazzo-Wigderson derandomization results implied a zero-one law for BPP: Either BPP=EXP and has measure one or there is sufficient derandomization to show BPP has measure zero.

The ideas do not directly work for the one-sided error class RP. The new Impagliazzo-Moser paper shows how to overcome these difficulties to get the zero-one law for RP. They also show that if RP does not have measure zero then not only RP but ZPP is equal to EXP. They also show some new derandomization if NP does not have measure zero, i.e., to get that AM = NP.

Complexity Papers Announced

The list of accepted papers for the 18th Annual IEEE Conference on Computational Complexity is now available. The conference will be held July 7-10 in Århus, Denmark and based on the titles of the accepted papers it should be an exciting meeting.

I will talk about a few of the more interesting papers in the weeks ahead. For now you can download many of these papers from the authors' web pages or from the ECCC.

More on Perfect Graphs

Today I saw Maria Chudnovsky give a talk at Princeton on her new result with Paul Seymour finding a polynomial-time algorithm for testing perfect graphs, a result I mentioned in an earlier post. The algorithm actually tests for Berge graphs which are graphs with no induced odd cycle of length at least five or the complement of such a graph. An earlier result of Chudnovsky, Robertson, Seymour and Thomas showed that a graph is perfect if and only if it is Berge. Otherwise the new algorithm does not use the techniques of the earlier paper.

The algorithm looks for some basic structures that would imply the graph is not Berge. If these structures don't exist then one does a cleaning process that simplifies the search for odd cycles. A cleaning process is described in another paper by Chudnovsky, Cornuéjols, Liu, Seymour and Vuškovic.

While the algorithm will test whether the graph is Berge, it is still open to determine whether a graph had an odd cycle of length at least five.

Chudnovsky's web page now has papers describing all of these results as well as other pointers on perfect graphs.

Complexity Class of the Week: BPPpath

Previous CCW

Let us call a nondeterministic Turing machine M balanced if for every input x, all of its computational paths have the same length, i.e., the number of nondeterministic bits depends only on x and not on previous guesses. We can define the characterize class BPP as follows:

L is in BPP if there is a balanced nondeterministic polynomial-time M such that

1. If x is in L then there are at least twice as many accepting as rejecting paths of M(x).
2. If x is not in L then there are at least twice as many rejecting as accepting paths of M(x).

Suppose we use the same definition without the "balanced" requirement. This gives us the class BPP_path studied mostly in a 1997 paper of Han, Hemaspaandra and Thierauf.

BPP_path contains BPP by definition but it contains much more. Let us show that SAT is contained in BPP_path.

Let φ be a formula with n variables. Consider the following machine M(φ): Guess an assignment a for φ. If a is rejecting then reject. If a is accepting then guess n+1 bits, ignore them and accept.

If φ is not satisfiable then M(φ) will only have rejecting paths. If φ is satisfiable then it will have at least 2ⁿ⁺¹ accepting paths and at most 2ⁿ-1 rejecting paths fulfilling the requirements of the definition of BPP_path.

Han, Hemaspaandra and Thierauf prove many other results about BPP_path. The class contains MA and P^NP[log] (P with O(log n) queries to an NP language like SAT). BPP_path is contained in P^Σ₂[log], BPP^NP and PP.

Whether BPP_path is contained in ZPP^NP or Σ₂ remain the most interesting open questions about this class.

News for Nerds. Stuff that Matters.

I noticed that Slashdot has recently mentioned some TCS research. This would therefore be theoretical computer science that matters to nerds.

The first was a pointer to Scienceblog article on the work of Roughgarden and Tardos on selfish routing. Here is their main example: Consider two roads from city A to city B. The first road takes an hour and the second road takes p hours, where p is the fraction of people who take the second road. The best way to route to minimize total travel time is for half the people to take the second road (average time = 3/4 hour). If everyone acts selfishly, the only equilibrium is everyone taking the second road for an average time of one hour. For more details see Tim Roughgarden's home page.

The other article pointed to Microsoft's research Penny Black Project which hopes to prevent spam by making sending email "expensive." The variation using complexity requires the sender to solve a moderately hard problem generated by the intended recipient.

Always keep in mind that what happens at Microsoft research, especially amongst the theoreticians, should not be read to imply any future email policy at Microsoft, no more than one can determine future NEC policies from my own research.

Traveling Salesman on the Plane

Yesterday's post on NP-complete problems reminds me of one of the more interesting open questions, the complexity of the traveling salesman problem on the plane.

The traveling salesman problem consists of a collection of n cities, a symmetric distance function d(i,j) and a number k. The question is whether there is an ordering of the cities so that a tour through those cities and back to the start can be done in total distance at most k. If d takes on rational values, the problem is NP-complete in general and for many restrictions of the possible functions for d, such as requiring d to have the triangle inequality.

Consider the case where the cities are given as points (x,y) in the plane and the distance function is the regular Euclidean distance, i.e.,

d((r,s),(u,v))=((r-u)²+(s-v)²)^1/2. It is open whether this traveling salesman problem on the plane is NP-complete. In most cases, it is easy to show the problem is in NP and more difficult to show it NP-hard. For TSP on the plane, Garey, Graham and Johnson showed it NP-hard way back in 1976; it remains open whether the problem is in NP.

In NP one can guess the ordering of the cities, the problem is in checking whether the sum of distances is at most k. Since we can approximate the square root to a polynomial number of digits the issue is how many digits of accuracy we need. So it boils down to the following purely mathematical question: Given an expression of length m over integers with addition, subtraction, squares and square roots (but no recursive squares or square roots) what is the smallest positive number than can be expressed? If the answer is at least 2^-mk for some k then TSP on the plane is in NP and NP-complete.

Let me also mention that one can well approximate traveling salesman on the plane.

Foundations of Complexity Lesson 15: More NP-complete Problems

Previous Lesson | Next Lesson

Now that we have shown that CNF-SAT is NP-complete we can use it to show many other problems are NP-complete via the following lemma.

Lemma: If a set A is NP-complete and B is in NP and A polynomial-time reduces to B then B is also NP-complete.

Proof: Let C be an arbitrary set in NP. We need to show C reduces to B. We know C reduces to A (since A is complete) and A reduces to B and it is a simple exercise to see that reductions are transitive. ◊

For example consider 3-SAT, the set of satisfiable 3-CNF formula with exactly 3 literals in each clause. 3-SAT is in NP by just guessing an assignment and verifying that it satisfies the formula. To show 3-SAT is NP-complete we will reduce 3-CNF to 3-SAT. We take each clause and convert it to a set of clauses each with three literals. We will add additional variables for this reduction.

If the clause C has three literals then no conversion is necessary.

If the clause C has two literals something like C = x OR y. We use a new variable z and replace C with two clauses, x OR y OR z and x OR y OR z. Notice that C is satisfied if and only if both new clauses can be satisfied.

If the clause C has one literal like C = x, we add two new variables, u and v and replace C with four new clauses, x OR u OR v, x OR u OR v, x OR u OR v and x OR u OR v.

If the clause C has k literals for k>3, we will replace C by two clauses, one with k-1 literals and one with 3 literals and then recurse. Suppose C = x₁ OR ... OR x_k. We add a new variable w and replace C with X₁ OR ... OR X_k-2 OR w and w OR x_k-1 OR x_k. Again note that C is satisfied only if both of the new clauses are satisfied with some value for w.

That is the reduction and the proof that it works is straightforward.

There are many many natural NP-complete problems and we could spend many lessons showing that they are NP-complete. Personally, I find NP-completeness proofs more algorithmic than complexity and I will instead focus on relationships of complexity classes in future lessons.

This site is a collection of optimization problems but it also gives you a good idea of what NP-complete problems are out there. The best source for all things NP-complete still remains the excellent book of Garey and Johnson.

NEXP not in P/poly?

Daniel Varga asks about the question of NEXP not in P/poly and whether it is "fundamentally" easier than NP not in P/poly. As a reminder: NEXP is the class of languages accepted in nondeterministic exponential (2^nO(1)) time. P/poly are languages accepted by nonuniform polynomial-size circuits, or equivalently by a polynomial time machine given a polynomial amount of "advice" that depends only on the input size.

First one must mention the beautiful paper of Impagliazzo, Kabanets and Wigderson that show that NEXP in P/poly if and only if NEXP equals MA.

NEXP not in P/poly should be much easier to prove than NP not in P/poly, as NEXP is a much larger class than NP. Also NEXP not in P/poly is just below the limit of what we can prove. We know that MA_EXP, the exponential time version of MA, is not contained in P/poly. MA_EXP sits just above NEXP and under some reasonable derandomization assumptions, MA_EXP = NEXP.

There is also the issue of uniformity. If one can use the nondeterminism to reduce the advice just a little bit than one could then diagonalize against the P/poly machine. Also if one could slightly derandomize MA machines than one could diagonalize NEXP from MA and thus from P/poly.

Still the problem remains difficult. BPP is contained in P/poly and we don't even know whether BPP is different than NEXP. Virtually any weak unconditional derandomization of BPP would separate it from NEXP but so far we seem stuck.

JACM is 50

For those with access to the Journal of the ACM, the fiftieth anniversary issue (Volume 50, Number 1) has a number of very short articles by prominent computer scientists on a number of interesting research issues in CS. In particular, articles by Steve Cook, Juris Hartmanis, Alexander Razborov, Peter Shor, Richard Stearns, Les Valiant and Andy Yao talk about problems directly related to this web log.

Yao's article "Classical Physics and the Church-Turing Thesis" is also available from ECCC. He makes some arguments (that I don't necessarily agree with) that there are some physical systems where Turing machines fail to capture computation.

While I was gone

The list of accepted papers of STOC has been posted. STOC and FOCS are the two most important annual theoretical computer science conferences. Quite a few interesting complexity papers. You can often download them by going to the authors' web sites.

From Scott Aaronson: I gave a talk to my brother's high school math club called "The Prime Facts: From Euclid to AKS." A writeup is available in case readers of your weblog are interested.

Last, but not least, we all are very saddened by the Columbia shuttle tragedy and the loss of seven brave people in the pursuit of science.

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.

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.

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.

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.

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.

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.

Supreme Court Rules on Infinity

Breaking news on a post from last October. The US Supreme Court ruled in favor of Disney that ever increasingly long finite lengths of copyright protection does not violate the constitutional prohibition against indefinite copyrights.

Our Friends at the NSA

Last weekend the movie Enemy of the State was shown on network television in the US. This is a pretty good thriller about a rogue NSA official using the resources of the NSA to get back some evidence from a lawyer innocently tangled up in this affair.

What do we know about the National Security Agency? While they don't have the best American mathematicians, who typically go to universities, they have a large collection of very good mathematicians. While they are free to read the same papers I read, we hear about very little of their work. They must have some exciting work in algorithms and complexity I can only dream about. Perhaps they have an efficient factoring algorithm or a working quantum computer in their basement. Unlikely, but possible.

Occasionally I meet NSA scientists at conferences, particularly those meetings devoted to quantum computation. "The NSA is much more interested in quantum computing than quantum cryptography," one such scientist told me. This surprised me since quantum cryptography seems much more likely to have real-world applications than quantum computers, both in theory and in practice. "The real issue is how long our current codes will remain unbreakable. We need to know if our the information currently encrypted will remain safe for 20 or 50 years."

So is Enemy of the State realistic? "Not at all," a different NSA employee told me at a quantum workshop shortly after the movie came out. "We work in boring cubicles, not the sleek offices depicted in the movie." Offices?! What about the satellites that can track people on the ground in real time? "No comment."

A Physics-Free Introduction to the Quantum Computation Model

I just posted to the BEATCS Complexity Column Web Page the February column, written by Steve Fenner, that gives an overview of quantum computing to those of us without a physics background.

Do you have a survey that you are dying to write? I am always looking for volunteers for the column.

Foundations of Complexity Lesson 13: Satisfiability

Previous Lesson | Next Lesson

Boolean-Formula Satisfiability (SAT) is the single most important language in computational complexity. Here is an example of a Boolean formula.

(u OR v) AND (u OR v)

u and v are variables that take on values from {TRUE, FALSE}. u means the negation of u. A literal is either a variable or its negation.

An assignment is a setting of the variables to true and false, for example (u→TRUE, v→FALSE). Once all of the variables are assigned a truth value, the formula itself has a truth value. The assignment (u→TRUE, v→FALSE) makes the formula above false. A satisfying assignment is an assignment that makes the formula true. For the formula above, the assignment (u→TRUE, v→TRUE) is satisfying. If a formula has a satisfying assignment we say the formula is satisfiable.

SAT is the set of satisfiable formula. The formula above is in SAT. This formula is not.

u AND (u OR v) AND (u or v)

A formula is in conjunctive normal form (CNF) if it is the AND of several clauses, each consisting of an OR of literals, like the formulas above. A disjunctive normal form (DNF) formula is the same with AND and OR reversed. A formula is k-CNF if every clause has exactly k literals. The first formula above is in 2-CNF.

CNF-SAT is the set of satisfiable CNF formulas. k-CNF-SAT or k-SAT is the set of satisfiable formulas in k-CNF.

Cook and Levin independently showed that SAT is NP-complete. The problem remains NP-complete if we restrict to CNF-SAT or even 3-SAT.

Next lesson we will show that CNF-SAT is NP-complete.

What is your Erdös number?

Well before the Kevin Bacon craze, mathematicians and theoretical computer scientists measured their worth by their distance from the great combinatorialist Paul Erdös. Your Erdös Number is defined inductively as follows

• Paul Erdös has an Erdös number of 0.
• If your Erdös number is not ≤ i and you have one or more co-authors with Erdös number i than your Erdös number is i+1.

My Erdös number is 2 as I have three co-authors who have written papers with Paul Erdös: Laszlo Babai, Mario Szegedy and Noga Alon. As Paul Erdös passed away in 1996, it is quite unlikely that it will decrease.

Jerry Grossman maintains a web page devoted to the Erdös number project.

Here is a conversation I once had with a colleague Carl Smith.
Carl: I think my Erdös number is 4.
Me: My Erdös number is 2.
Carl: My Erdös number is 3.

So what is your Erdös number? It is probably less than you think.

Circuits over Sets of Natural Numbers

Last October I mentioned an open problem of Pierre McKenzie. In short, consider a circuit whose wires contain subsets of the natural numbers. Inputs are {0} and {1}. The gates consist of union, intersection, complement, addition and multiplication. For sets A and B, A+B = {x+y | x in A and y in B} and A×B = {xy| x in A and y in B}.

Is the following problem decidable: Given such a circuit for a set A and a natural number w, is w in A?

Here is the paper by McKenzie and Klaus Wagner that describes this problem and gives results for many subcases. It will appear in the upcoming STACS Conference.

I have been haunted by the simplicity of the question and the difficult of the solution. Let me give you the proof (which I left as an exercise in the earlier post) that a decision procedure for the problem would yield a way to determine Goldbach's conjecture that every even number greater than 2 is a sum of two primes.

Define the set GE2 (the numbers at least 2) as {0}∪{1}. Define PRIMES as GE2∩GE2×GE2. Define GOLDBACH as (GE2×2)∩( PRIMES+PRIMES). Now we have Goldbach's conjecture is true if only if 0 is not in {0}×GOLDBACH.

Since I don't think Goldbach's conjecture has an easy decision procedure, I don't believe there is a decision algorithm for the problem. Proving this seems very tricky. The obvious idea is to try and create Diophantine equations. But even generating the set of squares is open.

When will we show P ≠ NP?

Given the comments from saturday's post, perhaps we should discuss the P versus NP question. I shouldn't have to explain the great importance of the P versus NP question to the readers of this web log, but people often wonder when it will be proved.

Like most complexity theorists, I strongly believe that P is not equal to NP, i.e., it is harder to search for a solution than verify it. Let me quote Juris Hartmanis in 1985, "We know that P is different from NP, we just don't know how to prove it."

We are further away from showing P ≠ NP then we have ever been. Let me explain this. In 1985 when I started graduate school, computational complexity theorists were in the midst of showing newer and stronger lower bounds on circuits. Furst, Saxe and Sipser in 1983 gave the first nontrivial lower bounds on bounded-depth circuits. In 1985, Yao followed soon after by stronger results of Hastad, gave exponential lower bounds. In 1986, Razborov showed that clique does not have small monotone circuits. In 1987, Razborov and Smolensky showed that parity could not be computed on bounded-depth circuits with Mod₃ gates. It seemed to many complexity theorists that the separation of P and NP was right around the corner.

But circuit lower bounds hit a brick wall. We have seen no significant progress on non-monotone circuit lower bounds since 1987. We have seen some new lower bounds in the past few years, using proposition proof complexity, branching programs, algebraic geometry and old-fashioned diagonalization, but all of these results are in models far too weak to even approach the complexity of the P versus NP question.

Settling the P versus NP question might require some branch of mathematics not even invented yet and that I would never have a prayer of understanding even the idea of the proof. When it will be proven cannot be predicted at all--it could be within a few years or maybe not in the next five hundred. It all depends on how long it will take to come up with the right new idea.

There are as many opinions on the future of the P versus NP question as there are theorists. Bill Gasarch has  collecting many of the opinions. It makes for an interesting read but you might as well ask Miss Cleo.

It is possible that P = NP is independent of the axioms of set theory. Doubtful I say, but that is a topic for another post.

Logic in the 21st Century

The June 2000 Association of Symbolic Logic Annual Meeting included a panel discussion on "The Prospects of Mathematical Logic in the Twenty-First Century". From that workshop came this paper, an interesting view of the future of logic. Richard Shore, Sam Buss, Anand Pillay and Alexander Kechris each wrote a section giving their views in the areas of recursion theory, proof theory, model theory and set theory respectively.

Mathematical Logic forms the foundation of computer science and the logic community often looks to the computer science community for directions and applications. The sections on recursion and proof theory really bring out this connection.

Foundations of Complexity Lesson 12: Turing Machine Redux

Previous Lesson | Next Lesson

Back in Lesson 1 we gave an informal description of a Turing machine as any computer program. That was fine for computability, but for complexity we need to give a more specific, but still informal, definition.

A one-tape Turing machine consists of an infinitely long "tape" consisting of tape cells that each can carry one of a finite set Γ of tape symbols. Typically we have Γ={0,1,B}. The Turing machine has a finite memory, where Q represents the set of all possible states of that memory. The Turing machine also has a tape head that points a specific location on the tape.

Initially the input is put somewhere on the tape with the rest of the tape having the special "B" blank symbol. The tape pointer points to the beginning of the input. The Turing machine starts out in some initial state q₀.

In each iteration the Turing machine looks at the tape character under the head and the current state. It writes a new character under the head and then moves the head one step left or right and then enters a new state depending on its instructions.

If the Turing machine enters the accept state q_a then it halts and accepts. If the Turing machine enters the reject state q_r then it halts and rejects. Otherwise the process repeats.

This simple model captures all of the computational power of much more general Turing machine. It also does this with at most a polynomial slow-down, i.e., if a problem of size n was solved in t(n) steps on a more complex machine it can be solved in time (t(n))^k on a one-tape Turing machine for some fixed k.

A deterministic Turing machine's choice of next state, character to write and direction to move the tape is a function of the previous state and current character under the tape. A nondeterministic machine may allow several options and if one series of options leads to acceptance we say the nondeterministic machine accepts.

A configuration of a Turing machine is a snapshot in time of the machine and consists of the tape contents, the current state and the location of the head pointer.

A tableau is a list of configurations

conf₀#conf₁#...#conf_m. A proper tableau for a machine M and input x is a tableau where

1. conf₀ is the initial configuration for M with input x.
2. conf_m is a configuration in the accept state.
3. For all i, 0 ≤ i < m, conf_i+1 follows from conf_i in one step.

A machine M accepts input x if and only if there is a proper tableau for M and x.

2003: A Year-Long Celebration of Geniuses

What do Alonzo Church, Andrey Kolmogorov and John von Neumann have in common?

1. They are all brilliant mathematicians.
2. Their research has helped establish the fundamentals of much of computer science.
3. They were all born in 1903.
4. All of the above.

Of course the answer is "All of the above." Throughout the year (in addition to the usual posts) we will honor these men and their research in the 100th anniversary of their births.

I almost added Frank Ramsey, also born in 1903, to the list. Certainly Ramsey Theory has played a major role in theoretical computer science. But the popularity of Ramsey Theory is due more to Paul Erd�s than to Ramsey who was mostly a philosopher.

Reflections on 2002

We have seen many exciting theorems during the past year but once again we have failed to prove that P≠NP or anything even close to it. There is always next year.

The most promising sign of the past year is the increased submissions and attendance at conferences pretty much across the board in theoretical computer science. The large number of students studying theory make of much of this increase. In the late 1990's during the dot-com boom, very few students, in particular Americans, went to graduate school in computer science. But with the days of easy money over and the need for computer science faculty still great, we have seen a large increase in the number of students. These students have and will continue to bring in new ideas and directions to our field. Let us hope there are enough jobs for all of them.

I also started this web log during this past year. Initially, I started this blog just to try out a new technology but I have had a blast writing these posts and sharing my knowledge and experiences. I hope you have enjoyed reading them. I don't understand how I rank so high on a Google search on "web log". Perhaps because "weblog" is supposed to be one word.

In remembrance: Edsger Dijkstra and Steve Seiden.

Have a good New Years everyone!

FOCS is going to Europe

In 2004 for the first time the FOCS conference will be held outside the United State or Canada. The 45th FOCS conference will be held in Italy. STOC held its first conference outside of North America in 2001 in Greece.

First some background on these conferences quoted from the preface of David Johnson's 1991 STOC/FOCS Bibliography.

Since the 1960's, two of the most important venues for presenting new results in theoretical computer science have been the annual STOC and FOCS conferences sponsored respectively by the Association for Computing Machinery and the IEEE Computer Society. "STOC" is an acronym standing for the ACM Symposium on Theory of Computing and "FOCS" stands for what is now called the IEEE Symposium on Foundations of Computer Science. The STOC Conference is organized by ACM's Special Interest Group on Automata and Computability Theory (SIGACT) and has been held every spring since 1969. The FOCS conference is organized by what is now called the IEEE Technical Committee on Mathematical Foundations of Computer Science (TC-MFCS) and is held in the fall. It began in 1960 as a "Symposium on Switching Circuit Theory and Logic Design" (SCT&LD), changed its name in 1966 to "Symposium on Switching and Automata Theory" (SWAT), and assumed its current name in 1975.

A few updates: SIGACT now stands for the Special Interest Group on Algorithms and Computation Theory. The 33rd STOC in 2001, besides being the first held outside the US or Canada, is also the first held in the summer. The SWAT acronym has been appropriated by the Scandinavian Workshop on Algorithm Theory.

FOCS and STOC have changed in other ways. Until the 80's, they were the only major outlet for conference papers in theoretical computer science. Now there are several specialized conferences including, of course, the IEEE Conference on Computational Complexity. Many researchers put a greater emphasis on their specialized conference than STOC and FOCS. This is somewhat true in complexity but much more so in say computational learning theory.

While most, but not all, of the best papers in theory still appear in STOC and FOCS, these conferences no longer reflect the broad interests of theoretical computer scientists. This was probably an inevitable outcome of a field maturing and becoming more specialized.

Find the Longest Path

How about some music? Here is an oldie but goodie. Daniel Barrett wrote Find the Longest Path during a final exam at Johns Hopkins in 1988. It is an algorithms song sung to the tune of Billy Joel's For the Longest Time. You can listen to the song  here 

A Note on Running Times

Suppose you have two papers to review that give algorithmic improvements for two different problems. Here n is the input size.

Paper A: Old Running Time was 4ⁿ. New Running time is 2ⁿ.

Paper B: Old Running Time was n⁴. New Running time is n².

Which paper gives the best improvement? This is not such an easy question to answer. Here are three ways to look at the question with three different results.

Analysis 1: Consider the improvement as a function of the input size: Old Running Time divided by New Running Time. Paper A is the clear winner with an improvement of 2ⁿ over the n² improvement of Paper B.

Analysis 2: Consider the improvement as a function of the old running time. Here we have a tie; in both papers the new running time is the square root of the old running time.

Analysis 3: Suppose we are interested in the largest problem we can solve with current technology. Fix a time t and consider the largest problem we can solve in time t. In the Paper A we go from (log t)/2 to log t, a factor of 2 improvement. Paper B does much better going from t^1/4 to t^1/2, a quadratic improvement.

Pictures of Manindra

Here is a sketch of Manindra Agrawal that I scanned in from the New York Times magazine article I mentioned last week. For contrast I added a photograph of Manindra and his student co-authors Neeraj Kayal and Nitin Saxena (from right to left) from the IIT Kanpur Primes in P page.

A complexity theorist immortalized in art. Brings tears to my eyes.

Rules for a Complex Quantum World

Michael Nielsen has a recent Scientific American article giving a very readable view of quantum information and computation. Nielsen is also co-author with Isaac Chuang of Quantum Computation and Quantum Information, the best book I've seen on the topic.

Foundations of Complexity Lesson 11: NP-Completeness

Previous Lesson | Next Lesson

Informally, NP-complete sets are the hardest sets in NP. What does it mean to be hardest? Here we use a polynomial-time version of reduction, a concept we first saw in Lesson 5.

Formally a language L is NP-complete if

1. L is in NP, and
2. For all A in NP, there is a polynomial-time computable function f such that x is in A if and only if f(x) is in L.

We say that f polynomial-time reduces A to L.

The following theorem captures the intuition for NP-completeness.
Theorem: Let L be an NP-complete language. Then L is in P if and only if P = NP.

Proof: If P = NP then since L is in NP then L is in P. Suppose L is in P and A is in NP. Let f be the reduction from A to L. We can then determine whether x is in A by testing whether f(x) is in L. ◊

In particular if any NP-complete set has an efficient algorithm then all NP-complete sets have efficient algorithms.

Do there exist NP-complete sets? Here is an example:

L = {(<M>,x,1^k) | M is a nondeterministic machine and M(x) accepts in k steps} Here 1^k is just a string consisting of exactly k 1's.

L is in NP by just simulating M(x) for k steps. If A is in NP, then A must be accepted by some nondeterministic machine M using time p(|x|) for some polynomial p. The reduction f is just f(x)=(<M>,x,1^p(|x|)).

L is not a natural language; you are unlikely to see it come up in any real-world application. In future lessons we will see that a large number of truly natural search problems are NP-complete which is why NP-completeness is perhaps the single most important concept to come out of theoretical computer science.

Ramsey Theory and Computer Science

Today we have a guest post from William Gasarch.

How many papers apply Ramsey Theory to Computer Science? If you said 37 and 4 surveys then you've probably visited www.cs.umd.edu/~gasarch/ramsey/ramsey.html where William Gasarch has a collection of such. A prominent theorist thinks there are over 100. Rather than argue the point, see if your favorite paper that applies Ramsey Theory is there, and if not then email the reference and if possible the paper or a link to it, to gasarch@cs.umd.edu.

The Great Journal Debate

Elsevier is closing down IDEAL the electronic access point for Academic Press, a publisher recently acquired by Elsevier. This leaves only Elsevier's Science Direct for electronic access of the Academic Press and other Elsevier journals. Given this news and today's New York Times article I feel I should comment on the great journal debate. As a member of the editorial board of Information and Computation, one of the Academic Press journals, these issues give me some angst.

The internet has, of course, a large effect on the distribution of scientific papers over the last ten years. Even more so, the consolidation of the scientific publishing companies has put a squeeze on university libraries.

Many of my colleagues have suggested that we just start up our own online journals. Running a journal is more than just getting papers refereed and sticking them on a web page. Journals have to be marketed, maintained and presented in a format that makes information easy to find. The private companies do a very good job of this. However, Elsevier's recent pricing policies are causing many libraries to drop several of their journals. Loss of access is never a good thing.

The professional societies, such as ACM, IEEE and SIAM have their own journals with their own on-line access policies that might form a reasonable median. You can also often get early versions of papers from scientist's home pages or sites like citeseer.

I have mixed emotions on the whole journal issue. Clearly status quo is not working--something will have to give. My biggest fear is that scientists will just stop submitting to journals altogether. I don't believe this is the best way to maintain knowledge for generations to come. After all, who will maintain your web page a century from now?

Outsider Math

The New York Times Magazine today highlights a year full of ideas, one of which is on the Agrawal et. al. primality algorithm under the title "Outsider Math". While Manindra might not have been an expert in number theory he was already an established member of the computational complexity community--certainly not an outsider in my mind.

Learning via Occam's Razor

I have been asked to expand upon the spam example from yesterday's Foundations of Complexity lesson. To do this let me go into a little background on computational learning theory.

The basic model for learning theory has examples given as strings and labelled positive or negative. From these labelled examples, one comes up with a hypothesis that hopefully will classify future examples well.

In PAC (Probably Approximately Correct) learning you want an algorithm that takes labelled examples generated by some distribution and will output some hypothesis that will high confidence will usually classify future examples drawn from the same distribution.

One simple approach is the Occam algorithm based on the Occam's Razor principle "when you have two competing theories which make exactly the same predictions, the one that is simpler is the better."

The Occam algorithm works by finding the smallest representation of a hypothesis consistent with the labelled examples and using that hypothesis to predict future examples. There is a theorem in learning theory that says this algorithm works well with the number of samples roughly the size of the smallest representation.

Let us focus on the problem of identifying spam using general circuits, a collection of AND, OR and NOT gates that capture computation. We'll talk more about circuits in a future lesson but just think of the running time of an algorithm as roughly the size of the equivalent circuit.

Given a collection of emails each labelled either as SPAM or NOT SPAM, the Occam algorithm requires us to find the smallest circuit that correctly labels all of these emails. In general finding such a circuit could be hard but under the assumption that P=NP this is an easy task. By the result mentioned above this circuit will likely classify SPAM correctly most of the time in the future.

Some caveats about this method.

• Why should there be a small circuit that characterizes spam? Well, I can look at an email and determine whether it is spam and my brain is just not that complex.
• The theorem only holds if the distribution we learn on is the same as the distribution we apply our circuit to. Spammers might change their spam to fool our new circuit. The P=NP assumption will make it easier for them as well.
• The P=NP assumption is probably not true.

For more information and details on computational learning theory check out the web site learningtheory.org and the resources mentioned on that site.

Foundations of ComplexityLesson 10: The P versus NP Problem

Previous Lesson | Next Lesson

In Lesson 8 we looked at the class P, the set of efficiently computable languages. In Lesson 9 we studied the class NP, the set of languages with efficiently verifiable proofs. Does P=NP, i.e., is every language with efficiently verifiable proofs computable efficiently?

The P versus NP question is the most important question in all of theoretical computer science and in mathematics in general. The Clay Mathematics Institute lists the P versus NP question as one of their seven Millennium Prize Problems. Determine whether P=NP and collect a million dollars.

To understand the importance of the P versus NP, let us imagine a world where P = NP.

• A large class of interesting search problems in NP, thought to be hard to solve, would have efficient solutions. These include Factoring, Map Coloring, Traveling Salesman, Job Scheduling and thousands of others. Half of Garey and Johnson is just a listing of NP-complete problems.
• Public key cryptography would be impossible.
• Learning via Occam's razor would be easy. For example if you wanted an algorithm for separating spam from useful email, just search for the smallest circuit that correctly identifies a large set of samples. You can do this if P=NP.

This is just the beginning. Of course the general consensus is that P≠NP but we have no idea on how to prove it.

Many of the future lessons will deal directly and indirectly with the P versus NP problem. With these lessons, I hope to give you a real feel of the importance and difficultly of this most important question.

FYI: The AIP Bulletin of Science Policy News

The American Institute of Physics produces a free electronic newsletter, FYI, covering science policy in the US. Although it has a physics bent, FYI does an amazing job educating the scientific community on how US science policy is set and what the current issues are. For example, check out this bulletin on the new NSF authorization bill.

Anyone interested or involved in science funding should subscribe to this newsletter. There is also a FYI This Month that gives a single monthly email highlighting the important FYI bulletins.

CAPTCHA in the Times

Today's New York Times carries a lengthy article about how Yahoo is using Manuel Blum's CAPTCHA project to prevent automated registrations. You saw it here first.

SIGACT News

The December SIGACT News is out, the first edited by David Haglin. Of interest to complexity theorists

• Lane Hemaspaandra's Complexity Theory Column has Part 2 of the Schaefer-Umans survey on Completeness in the Polynomial-Time Hierarchy.
• A book review of A New Kind of Science by Stephen Wolfram. "Its not new, its not science and its not kind."
• The Education Forum discusses a proposal for a Dagstuhl-like facility in the US and a preview of the Homer-Selman book Computability and Complexity Theory.
• Calls for nominations for the G�del Prize and Knuth Prize. Nominate your favorite complexity papers and theorists.

Complexity Class of the Week: MA

Previous CCW

MA gets its name from the Arthur-Merlin games developed by Babai. MA is an interactive proof system where the all-powerful Merlin sends a message that is verified by a probabilistic Arthur. Here is a formal definition.

A language L is in MA if there is a probabilistic polynomial-time machine M and a polynomial p such that for all strings x,

1. If x is in L then there is a w, |w|=p(|x|) and M(x,w) accepts with probability at least 2/3.
2. If x is not in L then for all w, |w|=p(|x|), M(x,w) accepts with probability at most 1/3.

As with many other interactive proof classes, the 1/3 can be replaced with a value exponentially small in |x| and the 2/3 can be replaced by 1.

The w is a proof that Merlin can write down and Arthur can verify years later without further interaction from Merlin. Sometimes MA is called the class of languages with publishable proofs.

Despite the naturalness of the class, there are no known natural problems in MA not known to be in NP∪BPP.

MA contains NP and BPP and also NP^BPP. MA is contained in its cousin class AM and thus BPP^NP. MA is also contained in many of the same classes BPP is contained in, including S₂, ZPP^NP, Σ₂∩Π₂ and PP. There are oracles where AM is not contained in these classes. Also none of these containments are tight in all relativized worlds.

If L is checkable and has polynomial-size circuit then L is in MA. I will leave the definition of checkable to another post but this implies

If EXP is in P/poly then EXP is in MA. We can replace EXP in the above statement with PSPACE or PP. Using the above statement one can show that MA_EXP does not have polynomial-size circuits. MA_EXP is like MA with polynomials replaced with exponentials.

A strong pseudorandom generator that derandomizes probabilistic circuits will also derandomize MA to NP. Using the result of Impagliazzo-Wigderson we get: If E require 2^{ε n} size circuits for some ε>0 then MA = NP.

The quantum version of MA, QMA has gotten some recent attention. Here Merlin sends entangled quantum bits and Arthur does quantum transformations and measurements. We will discuss QMA another day when it has its turn as complexity class of the week.

Bad Math Joke

There are 10 kinds of mathematicians: Those who understand binary notation and those that don't.

Foundations of ComplexityLesson 9: Nondeterminism

Previous Lesson | Next Lesson

To properly classify problems we will sometimes need to define models of computation that do not exist in nature. Such is the case with nondeterminism, the topic of this lesson.

A nondeterministic Turing machine can make guesses and then verify whether that guess is correct. Let us consider the map coloring problem. Suppose you are presented with a map of a fictitious world and you want to give each country a color so no two bordering countries have the same color. How many colors do you need?

The famous Four Color Theorem states that four colors always suffice. Can one do it in three?

Let L be the set of maps that are 3-colorable. A nondeterministic Turing machine can "guess" the coloring and then verify quickly for every bordering pair of countries that they have different colors.

We let NP be the class of problems that use nondeterministic polynomial time. We can give an equivalent definition of NP using quantifiers: L is in NP if there is a polynomial p and a deterministic Turing machine M such that for all x, x is in L if and only if there is a w, |w| ≤ p(|x|) and M(x,w) accepts in time at most p(|x|).

The string w is called a witness. In the case of map coloring, w is the coloring of the countries.

Can we solve map coloring in deterministic polynomial-time? Is every NP problem computable in deterministic polynomial-time? Therein lies the most important question of all, which we will discuss in the next lesson.

You can't judge a proceedings from its cover

Scott Aaronson writes an ode to the FOCS proceedings cover illustration and asks about the origin of the illustration. All I can say is that the FOCS cover has remained unchanged since at least my first FOCS conference in 1986.

I can give the history of the Complexity Conference cover which should be similar since Complexity and FOCS are both IEEE Computer Society conferences. When Complexity, then known as Structure in Complexity Theory, took on IEEE sponsorship in 1987, an IEEE artist took a look at the papers and came up with the cover with various symbols from the text. Here is a scan of the 1990 cover.

When Eric Allender took over the conference he rightly eliminated the strange symbols from the cover and in 1998 what is now the current cover first appeared.

If you are a budding artist and wish to redesign the complexity proceedings cover, we are always welcome to possibilities. If your cover is approved by the conference committee, you will be well acknowledged in the proceedings and bask in the glory of knowing your art work will live on in offices of complexity theorists around the world for generations to come.

Quantum Information Science and Technology Roadmap

The Quantum Information Science and Technology Roadmap version 1.0 is now publicly available. From the web site: The overall purpose of this roadmap is to help facilitate the progress of quantum computation research towards the quantum computer science era. It is a living document that will be updated annually.

Section 6.8 gives a nice overview of the theoretical computer science contributions to quantum computing.

CAPTCHA

Can you read the word above? Could a computer?

Manuel Blum won his Turing Award in 1995 for his work in computational complexity and its applications to cryptography. The theory of much of modern-day cryptography uses the assumption that certain problems are not easily computable to create unbreakable codes and protocols.

These days Blum is working on another project that also uses the assumption that some problems are hard computationally. The idea is to use problems that humans can solve easier than computers to prevent automated registration, voting, etc. Check out the CAPTCHA project web site.

Complexity Deadline

One last reminder that today is the submission deadline for the 2003 Conference on Computational Complexity. Good luck to all submitters.

Have a great Thanksgiving everyone!

Identity-Based Encryption

Dan Boneh gave a talk at Princeton today about some recent developments in cryptography based on algebraic geometry. One of these tools is identity-based encryption which is public-key encryption where the public key is just a user's identity such as their email address.

Dan's group has an implementation of the system for Outlook, Yahoo Mail and some other systems. If you want to be the first on your block using the latest and greatest encryption or just want more information check out the IBE web site.

Personally, I send all my email in cleartext. If anyone goes through the hassle of capturing it they will only discover what a boring person I am.

IAS

An article on the search for a new director of the Institute for Advanced Study discusses the changing nature of the institute.

The faculty member in computer science mentioned in the article is complexity theorist Avi Wigderson. It was a coup for complexity and all of computer science when he was appointed a faculty member in 1999. With a large collection of postdocs, visitors and students he has made the institute quite an exciting place for theoretical computer science and discrete math.

FOCS and Visas

The FOCS Conference, the major fall theory conference held last week in Vancouver, sounded like a complete success. According to PC Chair Bernard Chazelle there were 320 registrants--quite a healthy number for this conference. Most encouraging was the larger number of students attending as well as a number of strong student papers indicating a solid future for theoretical computer science.

The 320 does not count another 50 "registrants" from Nigeria. They registered with fake credit card numbers in order to obtain letters from the conference organizers to help them obtain visas to go in this case to Canada. Whether they got the visas is unclear and they, of course, never showed up at the conference.

The temptation to help those from Africa is strong, especially since that continent is woefully underrepresented in computer science. However we must as a community be diligent against those who use our conferences as a way to get around standard immigration laws. Whether or not we agree with those laws, if abuses of this nature continue it becomes harder to bring in legitimate scientists, a problem I discussed in my last post.

Coming to America

A recent Washington Post editorial brings up an important issue.

Andris Ambainis was supposed to spend the fall at MSRI in Berkeley but instead is enjoying his native Latvia. When Manindra Agrawal came to Boston last month to talk about his primality algorithm, he was supposed to bring along his student co-authors. Instead he came alone.

Worries about terrorism have caused the US government have made them more cautious about issuing visas and this has slowed down the visa process tremendously. Visa problems have always been a thorn for academics but this fall seems particularly bad.

I understand the need to be careful but when science is hindered by politics nobody is a winner.

Where was Cook's Talk?

In 1971, Steve Cook gave his conference presentation that showed that SAT was NP-complete. There it did not immediately stir up much excitement but it is, in retrospect, the single most important conference talk in this history of theoretical computer science. So when and where was this talk?

Steve Cook's paper The Complexity of Theorem Proving Procedures appeared at the Third Annual ACM Symposium on Theory of Computing (STOC) that was held May 3-5, 1971 in Shaker Heights, Ohio, a suburb of Cleveland.

Funda Ergun, a professor at Case Western Reserve, just purchased a house in Shaker Heights and wondered where exactly the conference took place. We got the answer from Bill Rounds, who was one of the local organizers of that conference.

It was (at I think Stouffer's hotel) at the intersection of Warrensville Center Road and Chagrin Boulevard, in the Van Aken center district. The hotel is now gone.

Here is a Mapquest map of that location.

Someday we will organize a P versus NP workshop in that area and make a pilgrimage to this site.

Foundations of ComplexityLesson 8: Efficient Computation

Previous Lesson | Next Lesson

In past lessons, we have studied the computable functions. Computable functions can take an arbitrary amount of time: What good is a program that will eventually give the correct answer but might not finish before the universe collapses?

Somehow we want to limit the amount of time or memory that a computer can use. Just giving a fixed bound does not work well. As technology improves and computers get faster and better, we expect to solve larger and larger problems in a reasonable amount of time. Hartmanis and Stearns, in their seminal paper on computational complexity, turn this around to come up with the right idea: Consider time and memory as functions of the size of the input.

The time a machine M takes on input x is just the number of computation steps that it takes before halting starting with input x. I am being very informal about what a "step" is. In a later lesson we will get into formal definitions of computers and steps but for now just use the idea of implementing one instruction.

The memory or space as we theorists call it is just the number of bits of storage used by M on a given input.

Edmonds gave an algorithm for the matching problem that ran in polynomial time: The number of steps used by the algorithm on a graph of size n is n^k for some k. He suggests that polynomial-time captures efficient computation.

We now define our first complexity class P as the set of all languages L for which machine exist that determine whether x is in L and halts in time polynomial in the length of x. The P has many nice properties: A polynomial-time algorithm that uses a polynomial-time subroutine remains in polynomial-time. Also P is robust, that is the class is the same no matter how you formally define your machines.

In these lessons, we will treat P as the class consisting of efficiently computable problems. More classes will come.

It all started with a machine...

Steve Homer and I have finally finished our chapter A Short History of Computational Complexity. It will eventually appear in a book collection on the history of mathematical logic.

You can also see a talk I gave at the 2002 Complexity Conference based on the paper.

Tic Tac Toe Variation

In my daughter's second grade math homework there was an interesting variation of Tic-Tac-Toe designed to teach addition and subtraction. Take a 3 x 3 grid and randomly give each square a different number between 2 and 18. We have two players X and O. Play goes as follows:

1. Player X chooses a number from 1 to 9.
2. Player O chooses a number from 1 to 9 that she had not picked before.
3. Player O adds that number and the last number picked from X and if that square is on the board and unmarked, that square is marked O.
4. Player X chooses a number from 1 to 9 that he had not picked before.
5. Player X adds that number and the last number picked from O and if that square is on the board and unmarked, that square is marked X.
6. Go to step 2.

Play ends when either X or O has three in a row and is declared a winner or when all the numbers run out and the game is declared a draw.

Here is an example:

12 |  5 | 7
-----------
14 | 11 | 3
-----------
4  | 13 | 9

X: picks 1, O: picks 3 (to make 4), X: 8 (11), O: 4 (12), X: 3 (7), O: 6 (9). At the point the board looks like:

 O |  5 | X
-----------
14 |  X | O
-----------
 O | 13 | O

Defensively X plays 2, Y: 1, X; 1, Y:2 and whatever X plays next Y has a forced win by making 13 or 14.

Despite the simplicity this is quite a challenging game. For every initial configuration, is there always a forced draw like in real Tic-Tac-Toe or do some configurations have a forced win for X or O? How complicated is it to compute an optimal strategy?

My daughter was frustrated at how hard it is to win this game but she shouldn't be ashamed--I couldn't figure out the best strategy either. Amazing what complicated things can come out of a second-grade class.

Kolmogorov Complexity Web Site

Can't get enough Kolmogorov Complexity. Check out Marcus Hutter's site on Kolmogorov Complexity and Solomonoff Induction. The site is a bit dated but contains many useful links and information about the Kolmogorov mailing list which still seems quite active.

The Union of Complexity Classes

We often see the intersection of two classes as an interesting class in and of itself. For example factoring is in NP∩co-NP. In some cases you get interesting equalities, like that ZPP is equal to RP∩co-RP. But we rarely see the union of two classes. Every wonder why?

In fact, no complexity class can be the nontrivial union of two other classes. To formalize and prove this statement we need some definitions.

Let A and B be subsets of {0,1}^*. We define the join, A⊕B, as the union of {0x | x is in A} and {1y | y is in B}. Given a set C we define the 0-projection of C as {x | 0x is in C} and the 1-projection of C as {y | 1y is in C}. Note that the 0-projection of A⊕B is just A and the 1-projection is just B.

Essentially every complexity class is closed under joins and projections. For example if A and B are in NP then A⊕B is also in NP. The fact that no complexity class is the nontrivial union of other classes follows from the following Lemma.

Lemma: Let E, F and G be classes of languages that are closed under joins and projections and G = E∪F. Then either G = E or G = F.

Proof: Suppose the lemma is false. Let A be a set in G-E and B be a set in G-F. Let C = A⊕B. We have that C is in G since G is closed under joins. Thus C is in either E or F. Suppose C is in E. Since E is closed under projections, we have A is in E a contradiction. If C is in F then B is in F also a contradiction.

Foundations of ComplexityLesson 7: The Recursion Theorem

Previous lesson | Next Lesson

Here we are in Lesson 7 and have not yet talked about complexity per se. I felt it important to give some background on computability theory not only for the importance of the results but also to introduce the basic concepts of Turing machines, diagonalization and reducibility. We will start complexity in the next lesson.

Let me end the discussion of computability by one of my favorite theorems. Suppose you wanted to create the ultimate computer virus that attacked any program and made it change its behavior. The recursion theorem states that no matter how powerful the virus, some program will remain unscathed. At first this seems impossible just by considering the function that simulates a program and then adds one to the answer. But this process will not affect the machine that never halts.

Theorem: Let f be any computable function. There is some Turing machine M such that

L(M) = L(f(<M>))

The recursion theorem, sometimes called the fixed-point theorem, has one of the most unintuitive proofs where I cannot explain why it works, only that it does.

Proof: Fix a computable function f. For each machine N, construct a Turing machine <R> that on input x, simulates N(<N>) to produce the description of a machine and simulates that machine on x. Let g(<N>) be the function that outputs <R>. Note that if N(<N>) halts then the programs described by g(<N>) and N(<N>) accept the same language.

Note that g is computable even if N(<N>) does not halt. Let T(x) be the machine that computes f(g(x)). We will let M be the machine described by g(<T>). Then we have that
M accepts input x if and only if
the machine described by g(<T>) accepts input x if and only if
the machine described by T(<T>) accepts input x if and only if
the machine described by f(g(<T>)) accepts input x (since T(x)=f(g(x))) if and only if
the machine described by f(<M>) accepts input x. QED

As an application, consider the function f(x) that outputs the description of a machine that accepts {x}. By the recursion theorem must be some M such that L(M) accepts exactly <M>. As an experiment, pick your favorite programming language and find a program that outputs its own code. By an argument based on the recursion theorem, such a task is always possible but it is trickier than it seems.

This ends the section on computability theory which is an exciting area of research in and of itself. For further reading the book of Homer and Selman goes into these ideas with some more detail and examples. For more advanced concepts I recommend the books of Soare, Odifreddi or Schoenfield.

STACS

The STACS Conference has just posted the list of accepted papers for their 20th conference. STACS alternates between France and Germany (and only some truth to the rumor that it alternates between great food and great organization). The upcoming 2003 conference will be held in Berlin, February 27 to March 1.

I have always considered STACS, the Symposium on Theoretical Aspects of Computer Science, the best venue for computational complexity in Europe. I have attended the conference many times and they consistently have several strong papers in the area as well a good attendance of complexity theorists from both Europe and America. You can see the weight complexity gets on the web page where "Computational and structural complexity" gets the same weight as "Algorithms and data structures, including: parallel and distributed algorithms, computational geometry, cryptography, algorithmic learning theory".

The ICALP conference has a longer history, a larger audience, more traditions and does a better job representing Europe as a whole. But the scope in ICALP is quite large and computational complexity often gets lost in the shuffle.

Complexity Class of the Week: SPP, Part II

Previous CCW

Last week we gave the history of the complexity class SPP and described GapP functions. This week we will give a definition of SPP and many of the class' amazing properties.

A language L is in SPP if there is a GapP function f such that

1. If x is in L then f(x)=1.
2. If x is not in L then f(x)=0.

That is if x is in L there is one more accepting than rejecting path. If x is not in L there are the same number of each.

If we used #P functions instead of GapP functions we have the definition of UP. SPP contains UP since every #P function is a GapP function. In fact SPP contains FewP and even Few where we don't believe such languages are in UP.

SPP is the smallest Gap-definable class, i.e., the smallest class that can be defined by GapP functions as above. There are a number of common Gap-definable classes, for example from the Zoo: ⊕P, AWPP, C₌P, ModP, Mod_kP, MP, AmpMP, PP, WPP and of course SPP. SPP is contained in all of these classes. AWPP is the smallest classical class known to contain BQP, the class of problems with efficient quantum algorithms, though it is not known if BQP is itself Gap-definable.

SPP is exactly equal to the low sets for GapP, i.e., SPP is exactly the set of oracles A such that for any NP machine M, the number of accepting minus the number of rejecting paths of M^A(x) is still an (unrelativized) GapP function. This means that SPP is low for all of the Gap-definable classes, for example that ⊕P^SPP = ⊕P. This also means that SPP is self-low: SPP^SPP = SPP which means SPP is closed under union, complement and in fact any Turing-reduction.

Kobler, Schoning and Toran showed that graph automorphism is in SPP and very recently Arvind and Kurur have show that graph isomorphism is in SPP. This means that graph isomorphism sits in and is in fact low for every Gap-definable class.

The decision tree version of SPP is interesting. A function f on n bits is in this class if there is a polynomial g with polylog degree such that f(x)=g(x) on all x in {0,1}^*. All such functions have low deterministic decision tree complexity--the first complexity application of a combinatorial lemma of Nisan and Szegedy. Applications of this result include relativized worlds where SPP does not have complete sets or where P = SPP and the polynomial-time hierarchy is infinite.

Foundations of ComplexityLesson 6: The Halting Problem

Previous Lesson | Next Lesson

Last lesson we learned about using reductions to show problems are hard. Now consider the most famous of undecidable problems, the halting problem:

L_H = {<M> | <M> eventually halts with blank tape as input} We will now show that L_H is not computable. We do this by reducing the universal language L_U to L_H where L_U is the set of pairs (<M>,x) such that M(x) accepts.

Given <M> and x, consider the following program:
Replace input with x.
Simulate M on x.
If M(x) accepts then halt.
If M(x) does not accept then go into an infinite loop.

Let us call this program N. Note that M(x) accepts if and only if N halts on blank tape.

Now here is the important point. Consider the function f that given <M> and x, will produce the program N. Even though M(x) and N may not halt the actual procedure that converts <M> and x to N is computable. This is just converting one program to another.

So we have that (<M>,x) is in L_U if and only if M(x) accepts if and only if N=f(<M>,x) halts on blank tape if and only if N is in L_H. Thus f reduces L_U to L_H and thus by the Lemma of Lesson 5, we have that L_H is not computable.

I consider the noncomputability of the halting problem to be the single most important result in theoretical computer science. There are some programs, of course, that are easy to determine whether or not they will halt. But in general, no matter how smart you are or fast the computers, it is simply impossible to analyze a piece of code and see if it will terminate.

Using similar techniques one can prove a general result known as Rice's Theorem: Every nontrivial property of the computably enumerable languages is undecidable. More formally
Rice's Theorem: Let P be any non-empty proper subset of the computably enumerable languages. Then the language

L_P = {<M> | L(M) is in P} is not computable.

For example the following languages are not computable:

• {<M> | L(M) is empty}
• {<M> | L(M) is computable}
• {<M> | L(M) is finite}

Conferences

November is a month for conference deadlines. The STOC conference has a submission deadline of November 6. STOC and FOCS, which is being held November 16-19, are the two major theoretical computer science conferences.

STOC this year is part of the 2003 Federated Computing Research Conference in San Diego in June. Several other theory conferences are also part of FCRC and many of them have deadlines in November or soon thereafter.

My favorite conference, The IEEE Conference on Computational Complexity, will be held in Denmark in July. Their submissions deadline is November 27.

In computer science in general and theoretical computer science in particular, conferences are the primary outlet for announcement and publication of results. Since computer science is a relatively young discipline, the field changes dramatically year to year and the usual long process of journal publications might often publish outdated work. More mature fields like mathematics and physics use journals as the primary source of publication.

The main disadvantage of the computer science system is that while computer scientists are encouraged to submit their work to refereed journals, many of the important papers in the area never make it that far.

There have been at least two recent major exceptions to this process. Alexander Razborov wrote a paper last spring on lower bounds on quantum communication complexity that would have been the best quantum paper in FOCS if not the best paper. Instead he chose to submit it directly to a journal, Izvestiya of the Russian Academy of Science: Mathematics. The Agrawal-Kayal-Saxena Primality Paper which would easily be the best paper at the upcoming STOC is not being submitted to a conference either but directly to Annals of Mathematics. "Why should I send it to a conference," Manindra Agrawal asks, "when everyone already knows the result?"

Are these two papers a trend? Are conferences less important as papers are easily available online? Or is computer science finally becoming a mature field?