There are no sparse NP_W-hard sets

DOI10.1007/3-540-44683-4_25MaRDI QIDQ4779151zbMATH OpenFDO

Authors Felipe Cucker, Dima Grigoriev

Publication date 25 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2136/21360285

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• There are no sparse NP\(_{w}\)-hard sets
• On the existence of hard sparse sets under weak reductions
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• Sparse hard sets for P: Resolution of a conjecture of Hartmanis
• Sparse Sets in : Relativizations
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• On f-sparse sets in NP-P
• scientific article; zbMATH DE number 1008513

Cited in

(2)

• On sparseness, reducibilities, and complexity
• There are no sparse NP\(_{w}\)-hard sets

This page was built for publication: There are no sparse \(\text{NP}_W\)-hard sets

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