Randomized and deterministic algorithms for the dimension of algebraic varieties
Randomized and deterministic algorithms for the dimension of algebraic varieties
复制标题
代数簇维数的随机和确定性算法
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
P. Koiran
中科院分区：
文献类型：
--
作者：
P. Koiran
我们证明了旧的和新的结果计算代数簇的维数的复杂性。特别地，我们证明了这个问题在C上的Blum-Shub-Smale计算模型中是NP-完全的，它允许一个s/sup O（1）/D/sup O（n）/确定性算法，并且对于整数系数的系统，它在广义黎曼假设下属于Arthur-Merlin类.前两个结果是基于一般的去随机化参数。
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.