Archive for October 16th, 2009

A conversation about complexity lower bounds, VI

October 16, 2009

The story so far: our three characters, :), 8) and :|, have discussed in detail an approach that 🙂 has to proving complexity lower bounds. At the beginning of the discussion, they established that the idea would be very unlikely to prove lower bounds for circuit complexity, which is what would be needed to prove that P\neNP. More recently, they have given arguments that strongly suggest that the idea cannot prove interesting new bounds even for weaker models. In this segment of the dialogue, they nevertheless consider what kinds of methods would be needed in order to prove lower bounds for circuit complexity (as opposed to formula complexity). They don’t really get anywhere, and this part of the discussion ends rather abruptly, but they mention one or two interesting facts along the way.


🙂 After all that, I have to say that I’m still slightly disappointed that it seems that even if the ideas I’ve been having could be got to work, they are most unlikely to show that P\neNP.

😐 I didn’t really understand why not. Can somebody remind me? (more…)