Weak completeness notions for exponential time

DOI10.1007/978-3-642-14165-2_43zbMATH Open1288.68077OpenAlexW1572133473MaRDI QIDQ3587403FDOQ3587403

Timur Bakibayev, Klaus Ambos-Spies

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

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

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)

Cited In (9)

• Nontriviality for exponential time w.r.t. weak reducibilities
• Comparing nontriviality for E and EXP
• The Density of Weakly Complete Problems under Adaptive Reductions
• Title not available (Why is that?)
• 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

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)