The Real Dimension Problem is NPR-complete.

Abstract : We show that computing the dimension of a semi-algebraic set of R^n is an NP-complete problem in the Blum-Shub-Smale model of computation over the reals. Since this problem is easily seen to be NPR-hard, the main ingredient of the proof is an NPR algorithm for computing the dimension.
Document type :
Reports
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102032
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:28 AM
Last modification on : Sunday, April 28, 2019 - 1:23:08 AM

File

RR1997-36.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102032, version 1

Collections

Citation

Pascal Koiran. The Real Dimension Problem is NPR-complete.. [Research Report] LIP RR-1997-36, Laboratoire de l'informatique du parallélisme. 1997, 2+12p. ⟨hal-02102032⟩

Share

Metrics

Record views

20

Files downloads

37