The Density of Weakly Complete Problems under Adaptive Reductions

DOI10.1137/S0097539797321547MaRDI QIDQ4507390zbMATH OpenOpenAlexFDO

Authors Jack H. Lutz, Yong Zhao, Yong Zhao

Publication date 18 October 2000

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

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

zbMATH Keywords

complexity classescomputational complexitypolynomial reductionsresource-bounded measureweakly complete problems

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 512813
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Weakly Hard Problems
• Weak completeness notions for exponential time
• Weakly complete problems are not rare

Cited in

(7)

• The power of adaptiveness and additional queries in random-self- reductions
• scientific article; zbMATH DE number 512813 (Why is no real title available?)
• Measure, Stochasticity, and the Density of Hard Languages
• Weakly Hard Problems
• The size of SPP
• Dimension, halfspaces, and the density of hard sets
• Counting martingales for measure and dimension in complexity classes

This page was built for publication: The Density of Weakly Complete Problems under Adaptive Reductions

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