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 PNP, 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 norm of a low-complexity function cannot be too large, at least when has order of magnitude . 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 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…)