Nonlevelable sets and immune sets in the accepting density hierarchy inNP

The complexity theoretic concept of levelability is introduced to the accepting density hierarchy inNP. A setA inNP islevelable with respect to densityu(n) if for every polynomial-time nondeterministic Turing machine (NTM)M that acceptsA there is a better NTMM forA that improves the accepting density ofM infinitely often from the density belowu(n) tou(n). We investigate the structural properties of nonlevelable sets inNP. A nonlevelable set must have a maximal complexity core, and its maximal cores must have relatively low complexity. Most naturalNP-complete sets are paddable and hence levelable with respect to the two lowest levels in the accepting density hierarchy. A relativized accepting density hierarchy is constructed to demonstrate the possibility of the existence of nonlevelable sets at each level of the hierarchy.This research was supported in part by the National Science Foundation under Grants MCS-8103479 and MCS-8103479A01.