Comparing nontriviality for E and EXP

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

zbMATH Keywords

completenessexponential timelinear-exponential-time classpolynomial-exponential-time classpolynomial-time reducibilitiesweak completeness

Mathematics Subject Classification ID

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