Separating NP-completeness notions under strong hypotheses
From MaRDI portal
Publication:5929911
DOI10.1006/jcss.1999.1674zbMath0971.68064MaRDI QIDQ5929911
Ambos-Spies, Klaus, Levke Bentzien
Publication date: 17 April 2001
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1999.1674
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A thirty year old conjecture about promise problems, The size of SPP, Collapsing and separating completeness notions under average-case and worst-case hypotheses, Comparing reductions to NP-complete sets, Autoreducibility of NP-complete sets under strong hypotheses, Bi-immunity separates strong NP-completeness notions, Hard sets are hard to find, Query-monotonic Turing reductions, Partial bi-immunity, scaled dimension, and NP-completeness