Randomized and deterministic algorithms for the dimension of algebraic varieties
Pascal Koiran · 2002
We prove old and new results on the complexity of computing the dimension of algebraic varieties. In particular, we show that this problem is NP-complete in the Blum-Shub-Smale model of computation over C, that it admits a s/sup O(1)/D/sup O(n)/ deterministic algorithm, and that for systems with integer coefficients it is in the Arthur-Merlin class under the Generalized Riemann Hypothesis. The first two results are based on a general derandomization argument.