A classification of complexity core lattices

DOI10.1016/0304-3975(86)90140-4zbMath0638.68033OpenAlexW1998915384MaRDI QIDQ1099613

Pekka Orponen

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90140-4

zbMATH Keywords

core latticespolynomial complexity core

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Nonlevelable sets and immune sets in the accepting density hierarchy inNP, The structure of generalized complexity cores, OnP-subset structures, On inefficient special cases of NP-complete problems, Resource bounded immunity and simplicity

Cites Work

• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• The structure of generalized complexity cores
• Immunity, Relativizations, and Nondeterminism
• Bi-immune sets for complexity classes
• The density and complexity of polynomial cores for intractable sets
• Hard-core theorems for complexity classes
• Optimal Approximations and Polynomially Levelable Sets
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• On Reducibility to Complex or Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets