On average polynomial time

One important reason to consider average case complexity is whether all or at least some signi cant part of NP can be solved e ciently on average for all reasonable distributions Let PP comp be the class of problems which are solvable in average polynomial time for every polynomial time computable input distribution Following the framework of Levin the above question can now be formulated as Is NP included in PP comp In this paper it is shown that PP comp contains P as a proper subset Thus even if P NP it is still possible that NP PP comp As a further step it is shown that PP comp is di erent from NP Therefore either NP is not solvable e ciently on average or since PP comp E E NP and hence NP is a proper subset of Exp