Weakly Hard Problems

DOI10.1137/S0097539793249700MaRDI QIDQ4862792zbMATH OpenFDO

Authors Jack H. Lutz

Publication date 1 February 1996

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

Full work available at URL https://doi.org/10.1137/S0097539793249700

zbMATH Keywords

martingale diagonalizationweak completeness

Mathematics Subject Classification ID

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

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

Cited in

(12)

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

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)