OnP-subset structures

Given a setA, we investigate the lattice structure formed by those of its subsets that belong to the complexity classP, taken modulo finite variations and ordered by inclusion. We show that up to isomorphism, only three structures are possible for this lattice. IfA isP-immune, itsP-subset structure degenerates to the trivial one-element lattice. IfA is almostP-immune but notP-immune (for instance, ifA is inP), itsP-subset structure is isomorphic to the countable atomless Boolean lattice. In all other cases theP-subset structure is isomorphic to ⁽⁾ , the weak countable power of. All natural intractable sets appear to fall in the third category. The results generalize to many other complexity classes, and similar characterizations hold for, e.g., the structures formed by recursive complexity cores.This research was supported in part by the Emil Aaltonen Foundation, the Academy of Finland, and the National Science Foundation under Grant No. MCS83-14272. Part of the work was carried out while the second author was visiting the Department of Mathematics, University of California at Santa Barbara.