Exponential-time and subexponential-time sets
From MaRDI portal
Publication:1261474
DOI10.1016/0304-3975(93)90125-DzbMath0774.68049MaRDI QIDQ1261474
Tian Liu, Bin Fu, Shouwen Tang
Publication date: 16 September 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- On one-one polynomial time equivalence relations
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- A comparison of polynomial time completeness notions
- Bi-immune sets for complexity classes
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- The density and complexity of polynomial cores for intractable sets
- Optimal Approximations and Polynomially Levelable Sets
- Completeness for nondeterministic complexity classes
- On Reducibility to Complex or Sparse Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Complete sets and closeness to complexity classes
- Complete problems and strong polynomial reducibilities