There are no sparse NPW-hard sets

Authors
Cucker, F Grigoriev, D
Citation
F. Cucker et D. Grigoriev, There are no sparse NPW-hard sets, SIAM J COMP, 31(1), 2001, pp. 193-198
Citations number
12
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
31
Issue
1
Year of publication
2001
Pages
193 - 198
Database
ISI
SICI code
0097-5397(20010729)31:1<193:TANSNS>2.0.ZU;2-K
Abstract
In this paper we prove that, in the context of weak machines over R, there are no sparse NP-hard sets.