Nontriviality for exponential time w.r.t. weak reducibilities

DOI10.1016/j.tcs.2012.05.022zbMath1294.68082OpenAlexW2139429469MaRDI QIDQ391074

Timur Bakibayev, Ambos-Spies, Klaus

Publication date: 10 January 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.05.022

zbMATH Keywords

Turing reducibilitybounded truth-table reducibilitymany-one reducibilitypolynomial exponential hierarchytruth-table reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (1)

Weak completeness notions for exponential time

Cites Work

• Unnamed Item
• Unnamed Item
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Comparing nontriviality for E and EXP
• A comparison of polynomial time completeness notions
• A comparison of polynomial time reducibilities
• On 1-truth-table-hard languages
• Nontriviality for Exponential Time w.r.t. Weak Reducibilities
• Weak Completeness Notions for Exponential Time
• Weakly Hard Problems

This page was built for publication: Nontriviality for exponential time w.r.t. weak reducibilities