A conversation about complexity lower bounds, III

The story so far: , 8) and have been discussing how it might be possible to prove lower bounds for formula or circuit complexity. They have come to some understanding of what a proof could not be like, and in particular they have looked at examples of proof attempts that are ruled out by the result of Razborov and Rudich on natural proofs. But has proposed basing a proof on the dual of the norm, with around Several observations have been made that suggest that this is very unlikely to work, but the approach has not been definitively killed off. In the next stage of the conversation, our characters investigate the approach in more detail, finding further ways to attack it. They end on an optimistic note, but that optimism will be shaken in later instalments of the dialogue.

Incidentally, I’ve decided to let the rate that I post instalments be governed by the statistics: when they suggest that most people who are going to read an instalment have done so, then I’ll post the next one. It’s not an exact science, of course.

*************************************************

Before we dismiss the norm for unbounded as a useful complexity measure, it still seems worth thinking about the following problem.

Problem. Let and be two Boolean functions. If and , then how big can be?

I suppose quite a nice feature of that problem is that you can start right at the bottom, with .