Nonlevelable sets and immune sets in the accepting density hierarchy inNP

Research paper by Ker-I Ko

Indexed on: 01 Dec '85Published on: 01 Dec '85Published in: Theory of Computing Systems


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.