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)

zbMATH Keywords

weak completenessmartingale diagonalization

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)

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