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
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
0 references
0.8699628114700317
0 references
0.768922746181488
0 references
0.7613481879234314
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