Nontriviality for exponential time w.r.t. weak reducibilities
From MaRDI portal
Publication:391074
DOI10.1016/j.tcs.2012.05.022zbMath1294.68082MaRDI 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
Turing reducibility; bounded truth-table reducibility; many-one reducibility; polynomial exponential hierarchy; truth-table reducibility
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D30: Other degrees and reducibilities in computability and recursion theory
Related Items
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