Exponential-time and subexponential-time sets

DOI10.1016/0304-3975(93)90125-DzbMath0774.68049OpenAlexW2004944884MaRDI QIDQ1261474

Shouwen Tang, Bin Fu, Tian Liu

Publication date: 16 September 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90125-d

zbMATH Keywords

exponential time complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Robustness of PSPACE-complete sets ⋮ Autoreducibility, mitoticity, and immunity

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

This page was built for publication: Exponential-time and subexponential-time sets