On P-subset structures

From MaRDI portal





Given a set A, we investigate the lattice structure formed by those of its subsets that belong to the complexity class P, taken modulo finite variations and ordered by inclusion. We show that up to isomorphism, only three structures are possible for this lattice. If A is P-immune, its P- subset structure degenerates to the trivial one-element lattice. If A is ``almost P-immune but no P-immune (for instance, if A is in P), its P- subset structure is isomorphic to the countable atomless Boolean lattice \({\mathcal B}\). In all other cases the P-subset structure is isomorphic to \({\mathcal B}^{(\omega)}\), the weak countable power of \({\mathcal B}\). 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 page was built for publication: On P-subset structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3789542)