On the cutting edge of relativization: The resource bounded injury method

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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