On P-subset structures (Q3789542)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4053591
Language Label Description Also known as
default for all languages
No label defined
    English
    On P-subset structures
    scientific article; zbMATH DE number 4053591

      Statements

      OnP-subset structures (English)
      0 references
      On P-subset structures (English)
      0 references
      0 references
      0 references
      1987
      0 references
      lattice structure
      0 references
      complexity class P
      0 references
      P-immune
      0 references
      almost P-immune
      0 references
      intractable sets
      0 references
      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.
      0 references

      Identifiers