Comparing nontriviality for E and EXP
From MaRDI portal
Publication:693048
DOI10.1007/s00224-011-9370-3zbMath1253.68137OpenAlexW1983486272MaRDI QIDQ693048
Timur Bakibayev, Ambos-Spies, Klaus
Publication date: 7 December 2012
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-011-9370-3
completenessexponential timelinear-exponential-time classpolynomial-exponential-time classpolynomial-time reducibilitiesweak completeness
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (2)
Nontriviality for exponential time w.r.t. weak reducibilities ⋮ Weak completeness notions for exponential time
Cites Work
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Almost everywhere high nonuniform complexity
- Resource bounded randomness and weakly complete problems
- Quantitative aspects of speed-up and gap phenomena
- Weak Completeness Notions for Exponential Time
- Measure, Stochasticity, and the Density of Hard Languages
- Weakly Hard Problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Comparing nontriviality for E and EXP