Duality methods for the membership problem
Duality methods for the membership problem
复制标题
隶属度问题的对偶方法
DOI：
10.1007/978-1-4612-0441-1_6
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
C. Sessa
中科院分区：
文献类型：
--
作者：
A. Dickenstein;C. Sessa
经典的问题，决定成员的任意多项式理想是EXPSPACE完全的。此外，通过给定理想的生成元找到多项式的表示的问题可能涉及双指数（变量数）度（[16]）。在计算任意多项式理想的Gröebner基时也会出现同样的困难（[11]）。这意味着，所有已知的技术，以决定成员资格，并找到表示多项式相对于一个给定的理想导致双指数（顺序时间）的最坏情况的复杂性。然而，如果基础代数簇的几何结构特别简单，例如，如果给定的理想是零维或完全相交，则可以找到复杂度低得多的算法（参见例如[7]，[9]）。这些改进是由于最近关于仿射版本的有效零星散射的进展（比较[18]和那里给出的参考文献）。
The classical problem of deciding membership to arbitrary polynomial ideals is EXPSPACE complete. Moreover, the problem of finding a representation of a polynomial by generators of a given ideal may involve doubly exponential (in the number of variables) degrees ([16]). The same difficulty arises when computing Gröebner bases of arbitrary polynomial ideals ([11]). This means that all known techniques to decide membership and to find representations of polynomials with respect to a given ideal lead to doubly exponential (sequential time) worst case complexities. However, if the geometry of the underlying algebraic variety is particularly simple, e.g. if the given ideal is zero dimensional or complete intersection, algorithms of considerably lower complexity can be found (see e.g. [7], [9]). The improvements are due to recent progress concerning affine versions of the effective Nullstellensatz (compare [18] and the references given there).