The real dimension problem is NPR-complete

Authors
Koiran, P
Citation
P. Koiran, The real dimension problem is NPR-complete, J COMPLEX, 15(2), 1999, pp. 227-238
Citations number
20
Categorie Soggetti
Engineering Mathematics
Journal title
JOURNAL OF COMPLEXITY
ISSN journal
0885064X → ACNP
Volume
15
Issue
2
Year of publication
1999
Pages
227 - 238
Database
ISI
SICI code
0885-064X(199906)15:2<227:TRDPIN>2.0.ZU;2-J
Abstract
We show that computing the dimension of a semi-algebraic set of R-n is a NP R- complete problem in the Blum-Shub-Smale model of computation ol-er the r eals. Since this problem is easily seen to be NPR-hard, the main ingredient of thr proof is a NPR algorithm for computing the dimension. (C) 1999 Acad emic Press.