SOME PROPERTIES OF SETS TRACTABLE UNDER EVERY POLYNOMIAL-TIME COMPUTABLE DISTRIBUTION

One important reason to consider average case complexity is the question whether all, or at least some significant part of NP can be solved efficiently on average for all reasonable distributions. Let P-p-camp be the class of problems, which are solvable in average polynomial-time for every polynomial-time computable input distribution. Following the framework of Levin (1986) the above question can now be formulated as: Is NP included in P-p-camp? In this paper, it is shown that P is a proper subset of P-p-camp. In contrast it holds that P-p-camp is equal to P on tally sets and therefore it can be shown that P-p-camp is properly contained in E. As a further property it is shown that P-p-camp is different from NP.