# Computational Complexity

### Thursday, January 09, 2003

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.

### Tuesday, January 07, 2003

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.

### Monday, January 06, 2003

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 Mod3 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 collected many of these 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.