On the cutting edge of relativization: The resource bounded injury method
From MaRDI portal
Publication:4632432
DOI10.1007/3-540-58201-0_74zbMath1420.68090OpenAlexW1773263865MaRDI QIDQ4632432
Harry Buhrman, Leen Torenvliet
Publication date: 29 April 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-58201-0_74
Related Items
Separating classes in the exponential-time hierarchy from classes in PH ⋮ Index sets and presentations of complexity classes ⋮ Results on resource-bounded measure
Cites Work
- The strong exponential hierarchy collapses
- A Turing machine time hierarchy
- On truth-table reducibility to SAT
- The polynomial-time hierarchy
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- On the random oracle hypothesis
- On Relativized Polynomial and Exponential Computations
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- On relativized exponential and probabilistic complexity classes
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Separating Nondeterministic Time Complexity Classes
- IP = PSPACE
- On the Computational Complexity of Algorithms
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item