### Thursday, January 09, 2003

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

8:02 AM
#
Comments
[]

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

3:21 PM
#
Comments
[]

### 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 Mod_{3} 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.

1:35 PM
#
Comments
[]