Weakly Hard Problems

DOI10.1137/S0097539793249700zbMATH Open0845.68048MaRDI QIDQ4862792FDOQ4862792

Authors: Jack H. Lutz 

Publication date: 1 February 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• The Density of Weakly Complete Problems under Adaptive Reductions
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Weak completeness notions for exponential time
• Weak completeness notions for exponential time

zbMATH Keywords

weak completenessmartingale diagonalization

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (12)

• Nontriviality for exponential time w.r.t. weak reducibilities
• Comparing nontriviality for E and EXP
• An excursion to the Kolmogorov random strings
• Baire categories on small complexity classes and meager-comeager laws
• The Density of Weakly Complete Problems under Adaptive Reductions
• A note on measuring in P
• Weak completeness notions for exponential time
• Weak completeness notions for exponential time
• Almost complete sets.
• Equivalence of measures of complexity classes
• Weakly useful sequences
• Weakly complete problems are not rare

This page was built for publication: Weakly Hard Problems

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