Weak completeness notions for exponential time

DOI10.1007/978-3-642-14165-2_43MaRDI QIDQ3587403zbMATH OpenOpenAlexFDO

Authors Klaus Ambos-Spies, Timur Bakibayev

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL http://archiv.ub.uni-heidelberg.de/volltextserver/10499/1/thesis.pdf

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)

Recommendations

• Weak completeness notions for exponential time
• Weakly Hard Problems
• scientific article; zbMATH DE number 1759402
• Nontriviality for Exponential Time w.r.t. Weak Reducibilities
• Weakly complete problems are not rare

Cited in

(10)

• Nontriviality for exponential time w.r.t. weak reducibilities
• Comparing nontriviality for E and EXP
• The Density of Weakly Complete Problems under Adaptive Reductions
• scientific article; zbMATH DE number 1759402 (Why is no real title available?)
• Weak completeness notions for exponential time
• Weakly complete problems are not rare
• Nontriviality for Exponential Time w.r.t. Weak Reducibilities
• Weakly Hard Problems
• QUIXO is EXPTIME-complete
• Genericity and measure for exponential time (extended abstract)

This page was built for publication: Weak completeness notions for exponential time

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