Nonlevelable sets and immune sets in the accepting density hierarchy inNP

DOI10.1007/BF01699469zbMath0586.68043OpenAlexW2092583861MaRDI QIDQ3711750

Ker-I. Ko

Publication date: 1985

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01699469

zbMATH Keywords

time complexitypaddabilitycomplexity coreslevelabilitylevelable with respect to a density function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (6)

The structure of generalized complexity cores ⋮ Notes on polynomial levelability ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ On inefficient special cases of NP-complete problems ⋮ Resource bounded immunity and simplicity

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• Oracle-dependent properties of the lattice of NP sets
• BPP and the polynomial hierarchy
• A low and a high hierarchy within NP
• A classification of complexity core lattices
• On counting problems and the polynomial-time hierarchy
• The polynomial-time hierarchy
• A hierarchy for nondeterministic time complexity
• Immunity, Relativizations, and Nondeterminism
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Hard-core theorems for complexity classes
• Optimal Approximations and Polynomially Levelable Sets
• The Complexity of Enumeration and Reliability Problems
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Completeness, Approximation and Density
• Relativized Questions Involving Probabilistic Algorithms
• On the Accepting Density Hierarchy in NP
• On Reducibility to Complex or Sparse Sets
• On complexity properties of recursively enumerable sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Computational Complexity of Probabilistic Turing Machines
• Separating Nondeterministic Time Complexity Classes
• Computational complexity, speedable and levelable sets

This page was built for publication: Nonlevelable sets and immune sets in the accepting density hierarchy inNP