Nontriviality for exponential time w.r.t. weak reducibilities

DOI10.1016/J.TCS.2012.05.022MaRDI QIDQ391074zbMATH OpenOpenAlexFDO

Authors Timur Bakibayev, Klaus Ambos-Spies

Publication date 10 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.05.022

zbMATH Keywords

bounded truth-table reducibilitymany-one reducibilitypolynomial exponential hierarchytruth-table reducibilityTuring reducibility

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Nontriviality for Exponential Time w.r.t. Weak Reducibilities
• Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
• Weak completeness notions for exponential time
• Weak completeness notions for exponential time
• scientific article; zbMATH DE number 1962844
• scientific article; zbMATH DE number 4119625
• Strong time bounds: Non-computable bounds and a hierarchy theorem
• scientific article; zbMATH DE number 1072532
• Relativizations comparing NP and exponential time

Cites work

• A comparison of polynomial time completeness notions
• A comparison of polynomial time reducibilities
• Comparing nontriviality for E and EXP
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• Nontriviality for Exponential Time w.r.t. Weak Reducibilities
• On 1-truth-table-hard languages
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Weak completeness notions for exponential time
• Weakly Hard Problems

Cited in

(6)

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• Weak completeness notions for exponential time
• Nontriviality for Exponential Time w.r.t. Weak Reducibilities
• Towards the Actual Relationship Between NP and Exponential Time
• Comparing nontriviality for E and EXP
• \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly

This page was built for publication: Nontriviality for exponential time w.r.t. weak reducibilities

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