There are No Sparse NPw-Hard Sets
From MaRDI portal
Publication:2784447
DOI10.1137/S0097539700379346zbMath0992.68061MaRDI QIDQ2784447
Felipe Cucker, Dima Yu. Grigoriev
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (2)
On sparseness and Turing reducibility over the reals ⋮ On sparseness, reducibilities, and complexity
This page was built for publication: There are No Sparse NPw-Hard Sets
