Exponential-time and subexponential-time sets

DOI10.1016/0304-3975(93)90125-DMaRDI QIDQ1261474zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1072532
• Weak completeness notions for exponential time
• scientific article; zbMATH DE number 1962844
• scientific article; zbMATH DE number 1759402
• scientific article; zbMATH DE number 512826

Cites work

• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 176522 (Why is no real title available?)
• A comparison of polynomial time completeness notions
• Bi-immune sets for complexity classes
• Complete problems and strong polynomial reducibilities
• Complete sets and closeness to complexity classes
• Completeness for nondeterministic complexity classes
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On Reducibility to Complex or Sparse Sets
• On one-one polynomial time equivalence relations
• Optimal Approximations and Polynomially Levelable Sets
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• The density and complexity of polynomial cores for intractable sets

Cited in

(3)

• Autoreducibility, mitoticity, and immunity
• Robustness of PSPACE-complete sets
• A model of \(\widehat{R}^2_3\) inside a subexponential time resource

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1261474)