Randomized and deterministic algorithms for the dimension ofalgebraic varieties

摘要

We prove old and new results on the complexity of computing thedimension of algebraic varieties. In particular, we show that thisproblem is NP-complete in the Blum-Shub-Smale model of computation overC, that it admits a sO(1)DO(n) deterministicalgorithm, and that for systems with integer coefficients it is in theArthur-Merlin class under the Generalized Riemann Hypothesis. The firsttwo results are based on a general derandomization argument