|
NeuroCOLT
Technical Report NC-TR-98-006
The
Real Dimension Problem is NPR-Complete
Pascal Koiran
ENS Lyon
Keywords:
Blum-Shub-Smale model; NPR-complete
Received:
06-MAR-1998
Abstract
We show that computing the dimension of a semi-algebraic set of r^n
is a NPR-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 a NPR algorithm for computing
the dimension.
Download Compressed Postscript
|