8 Jan 2003 Bram   » (Master)

Lance Fortnow links to some interesting commentary on P vs. NP.

I found out today the standard terminology for my favorite conjecture -

Conjecture: The circuit complexity of the k-sum problem is at least n ** k.

This directly implies that the 4SUM problem is quadratic. I believe that the 3SUM problem is also quadratic (as does everybody), but that the reasons for that are much deeper and more complex.

It also implies P != NP, so we can rest assured that noone has proven it yet.

Given the obviousness of this conjecture I'm sure circuit complexity people have already spent considerable time on it and just haven't gotten anywhere, although curiously googling for '3sum' and 'circuit complexity' doesn't turn up anyone else musing on the subject.

Here is a good list of open problems to spend time on.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!