Weakly Hard Problems

DOI10.1137/S0097539793249700zbMath0845.68048MaRDI QIDQ4862792

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)

Related Items (9)

Equivalence of measures of complexity classes ⋮ An excursion to the Kolmogorov random strings ⋮ A note on measuring in P ⋮ Nontriviality for exponential time w.r.t. weak reducibilities ⋮ Almost complete sets. ⋮ Baire categories on small complexity classes and meager-comeager laws ⋮ Comparing nontriviality for E and EXP ⋮ Weakly useful sequences ⋮ Weak completeness notions for exponential time

This page was built for publication: Weakly Hard Problems