Weak completeness notions for exponential time

DOI10.1007/S00224-019-09920-4MaRDI QIDQ2322715zbMATH OpenOpenAlexWikidataFDO

Authors Timur Bakibayev, Klaus Ambos-Spies

Publication date 5 September 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

completenessreductionsexponential timeresource-bounded measureweak completenessalmost everywhere complexitylinear exponential time

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) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Weak completeness notions for exponential time
• scientific article; zbMATH DE number 1759402
• Comparing nontriviality for E and EXP
• Nontriviality for Exponential Time w.r.t. Weak Reducibilities
• Nontriviality for exponential time w.r.t. weak reducibilities

Cites work

• scientific article; zbMATH DE number 4010508 (Why is no real title available?)
• scientific article; zbMATH DE number 4037840 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 3995648 (Why is no real title available?)
• scientific article; zbMATH DE number 841081 (Why is no real title available?)
• scientific article; zbMATH DE number 1390028 (Why is no real title available?)
• A comparison of polynomial time completeness notions
• An excursion to the Kolmogorov random strings
• Comparing nontriviality for E and EXP
• Honest polynomial time reducibilities and the \(P=?NP\) problem
• Measure, Stochasticity, and the Density of Hard Languages
• Nontriviality for exponential time w.r.t. weak reducibilities
• On the Structure of Polynomial Time Reducibility
• Resource bounded randomness and weakly complete problems
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Weak completeness notions for exponential time
• Weakly Hard Problems

Cited in

(10)

• scientific article; zbMATH DE number 1759402 (Why is no real title available?)
• Nontriviality for exponential time w.r.t. weak reducibilities
• Nontriviality for Exponential Time w.r.t. Weak Reducibilities
• Comparing nontriviality for E and EXP
• QUIXO is EXPTIME-complete
• Weakly complete problems are not rare
• Weak completeness notions for exponential time
• Weakly Hard Problems
• Exponential-time and subexponential-time sets
• Lowness Properties of Sets in the Exponential-Time Hierarchy

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 Q2322715)