Separating Complexity Classes Using Autoreducibility
From MaRDI portal
Publication:4943880
DOI10.1137/S0097539798334736zbMath0949.68068arXivmath/9807185MaRDI QIDQ4943880
Harry Buhrman, Leen Torenvliet, Dieter van Melkebeek, Lance J. Fortnow
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9807185
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets, Autoreducibility, mitoticity, and immunity, On the autoreducibility of functions, Autoreducibility of NP-complete sets under strong hypotheses, Non-uniform reductions, Autoreducibility and mitoticity of logspace-complete sets for NP and other classes, Introduction to Autoreducibility and Mitoticity