A classification of complexity core lattices (Q1099613): Difference between revisions

\textit{N. Lynch} [J. Assoc. Comput. Mach. 22, 341-345 (1975; Zbl 0311.68037)] has shown that every recursive set A not in P contains an infinite polynomial complexity core: a set of elements \(C\subset A\) such that any algorithm deciding A needs more than polynomial time almost everywhere on C. Actually, any A not in P contains infinitely many different cores, the collection of which forms a lattice under inclusion. We study the structure of this lattice, proving that, surprisingly, there are only three possibilities: assuming the lattice is not trivial (which happens if A is in P), its shape depends only on whether A is `almost P- immune' or not. It is known that the natural intractable sets usually do not have this property.