On lower bounds of the closeness between complexity classes
From MaRDI portal
Publication:4032931
DOI10.1007/BF01202282zbMath0771.68050MaRDI QIDQ4032931
Publication date: 17 May 1993
Published in: Mathematical Systems Theory (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Probabilistic complexity classes and lowness
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- PP is as Hard as the Polynomial-Time Hierarchy
- On Sets Truth-Table Reducible to Sparse Sets
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Complete Problems and Strong Polynomial Reducibilities
- Complete sets and closeness to complexity classes