A classification of complexity core lattices
From MaRDI portal
Publication:1099613
DOI10.1016/0304-3975(86)90140-4zbMath0638.68033OpenAlexW1998915384MaRDI QIDQ1099613
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
Analysis of algorithms and problem complexity (68Q25) Recursively (computably) enumerable sets and degrees (03D25)
Related Items (5)
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
This page was built for publication: A classification of complexity core lattices