Average-case complexity and instance complexity

Abstract

This thesis characterizes the set of problems that are decidable in average polynomial time in terms of the instance complexities of their individual instances. Different approaches are investigated and the relationships among them are shown. It is shown that almost every instance of almost every problem in exponential time has essentially maximal instance complexity. Using these results, it is shown that the set of problems decidable in average polynomial time with respect to a particular probability distribution has measure 0 in exponential time.