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
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Autoreducibility and mitoticity of logspace-complete sets for NP and other classes ⋮ Autoreducibility, mitoticity, and immunity ⋮ Introduction to Autoreducibility and Mitoticity ⋮ Non-uniform reductions ⋮ Autoreducibility of NP-complete sets under strong hypotheses ⋮ On the autoreducibility of functions ⋮ Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
