ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01692061
Permalink
