scientific article; zbMATH DE number 1834655

zbMATH Open0999.68082MaRDI QIDQ4779151FDOQ4779151

Authors: Felipe Cucker, Dima Grigoriev 

Publication date: 25 November 2002

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

Title of this publication is not available (Why is that?)

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
• scientific article; zbMATH DE number 1088261
• scientific article; zbMATH DE number 1107624
• scientific article; zbMATH DE number 1008513

Mathematics Subject Classification ID

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

Cited In (2)

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

This page was built for publication:

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