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…)


Follow

Get every new post delivered to your Inbox.

Join 1,562 other followers