Resource bounded immunity and simplicity
From MaRDI portal
Publication:2576870
DOI10.1016/j.tcs.2005.03.055zbMath1080.68043MaRDI QIDQ2576870
Tomoyuki Yamakami, Toshio Suzuki
Publication date: 29 December 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.03.055
68Q25: Analysis of algorithms and problem complexity
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Oracle-dependent properties of the lattice of NP sets
- A low and a high hierarchy within NP
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- A classification of complexity core lattices
- On simple and creative sets in NP
- Diagonalizations over polynomial time computable sets
- Simplicity, immunity, relativizations and nondeterminism
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- A taxonomy of complexity classes of functions
- Classes bounded by incomplete sets
- Defying upward and downward separation
- Generic separations
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- Simplicity, Relativizations and Nondeterminism
- Bi-immune sets for complexity classes
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- Optimal Approximations and Polynomially Levelable Sets
- A second step toward the strong polynomial-time hierarchy
- The Boolean Hierarchy I: Structural Properties
- 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
- Structural properties for feasibly computable classes of type two
- A note on balanced immunity
- On Reducibility to Complex or Sparse Sets
- On the Structure of Polynomial Time Reducibility
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- Instance complexity
- Strong self-reducibility precludes strong immunity
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Recursively enumerable sets of positive integers and their decision problems
- [Russian Text Ignored]
