The Density of Weakly Complete Problems under Adaptive Reductions

DOI10.1137/S0097539797321547zbMath0976.68073OpenAlexW1965623355MaRDI QIDQ4507390

Jack H. Lutz, 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

computational complexitycomplexity classesresource-bounded measurepolynomial reductionsweakly complete problems

Mathematics Subject Classification ID

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

Related Items (2)

The size of SPP ⋮ Dimension, halfspaces, and the density of hard sets

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