There are no sparse NPW-hard sets
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 193-198 |
| Journal / Publication | SIAM Journal on Computing |
| Volume | 31 |
| Issue number | 1 |
| Publication status | Published - 2001 |
Link(s)
Abstract
In this paper we prove that, in the context of weak machines over R, there are no sparse NP-hard sets. © 2001 Society for Industrial and Applied Mathematics.
Research Area(s)
- Real number computations, Structural complexity
Citation Format(s)
There are no sparse NPW-hard sets. / Cucker, Felipe; Grigoriev, Dima.
In: SIAM Journal on Computing, Vol. 31, No. 1, 2001, p. 193-198.
In: SIAM Journal on Computing, Vol. 31, No. 1, 2001, p. 193-198.
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
