On P-subset structures
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.
- A classification of complexity core lattices
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Bi-immune sets for complexity classes
- Completeness, Approximation and Density
- scientific article; zbMATH DE number 4010508 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Immunity, Relativizations, and Nondeterminism
- On Isomorphisms and Density of NP and Other Complete Sets
- On Reducibility to Complex or Sparse Sets
- On splitting recursive sets
- Optimal Approximations and Polynomially Levelable Sets
- Oracle-dependent properties of the lattice of NP sets
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- The complexity of theorem-proving procedures
- The density and complexity of polynomial cores for intractable sets
- Unit Refutations and Horn Sets
- A classification of complexity core lattices
- The structure of generalized complexity cores
- The algebraic structure of the isomorphic types of tally, polynomial time computable sets
- On inefficient special cases of NP-complete problems
- Set-theoretic structure of computable sets
- Characterizations and existence of easy sets without hard subsets
- scientific article; zbMATH DE number 3885884 (Why is no real title available?)
- scientific article; zbMATH DE number 4197420 (Why is no real title available?)
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)