Archive for October 7th, 2009

A conversation about complexity lower bounds, IV

October 7, 2009

This is the fourth part of a dialogue between three characters ๐Ÿ™‚ (a mathematical optimist who likes to suggest approaches to problems), 8) (a more sceptical mathematician who knows a small amount of theoretical computer science), and ๐Ÿ˜ (an onlooker who occasionally asks for more detail, and occasionally makes comments about what ๐Ÿ™‚ and 8) say). They are discussing the possibility of proving lower bounds for computational complexity. ๐Ÿ™‚ wanted at first to prove that P\neNP, but has now been persuaded that proving a lower bound for formula size is a more realistic target, at least for the time being, and is still a major unsolved problem. In part II of the conversation, ๐Ÿ™‚ proposed trying to show that the dual of the U^k norm of a low-complexity function cannot be too large, at least when k has order of magnitude \log n. Numerous problems have been identified with this approach, but the idea has not yet been completely killed off. We return to the conversation as a new topic is introduced. This instalment is shorter than average, so I’ll probably post the next instalment sooner than average.


8) You know, something has been bothering me about our discussion so far.

๐Ÿ™‚ You’ve made that pretty clear.

8) I’m not talking about the fact that you don’t have any heuristic argument in favour of the U^{C\log n} dual norm being a useful complexity measure, but about something else that would be equally fundamental to any lower bound proof.

๐Ÿ™‚ What’s that?

8) Well, you haven’t said how you would go about proving that some function in NP has a large norm. (more…)