A cofactor representation of an ideal element, that is, a representation in terms of the generators, can be considered as a certificate for ideal membership. Such a representation is typically not unique, and some can be a lot more complicated than others. In this work, we consider the problem of computing sparsest cofactor representations, i.e., representations with a minimal number of terms, of a given element in a polynomial ideal. While we focus on the more general case of noncommutative polynomials, all results also apply to the commutative setting. We show that the problem of computing cofactor representations with a bounded number of terms is decidable and NP-complete. Moreover, we provide a practical algorithm for computing sparse (not necessarily optimal) representations by translating the problem into a linear optimization problem and by exploiting properties of signature-based Gr\"obner basis algorithms. We show that for a certain class of ideals, representations computed by this method are actually optimal, and we present experimental data illustrating that it can lead to noticeably sparser cofactor representations.
翻译:理想元素的共构体表示, 即生成方的表示, 可以被视为理想会员资格的证明。 这种表示通常不是独一无二的, 某些代表可能比其他更复杂。 在这项工作中, 我们考虑在多元理想中计算稀少的共构体表示, 即以最小数量表示, 某个元素的表示, 在多义理想中 。 虽然我们关注非交替性多义的比较一般的情况, 但所有结果也都适用于通俗环境 。 我们表明, 计算有一定数量术语的共构体表示的问题是可以消化的, 并且是NP 完成的。 此外, 我们通过将问题转化为线性优化问题, 以及利用基于签名的 Gr\\"obner 基算法的特性, 为计算稀有( 不一定是最佳的) 提供了一种实用的算法 。 我们显示, 对于某类理想, 由这种方法计算的表示其实是最佳的, 我们提供实验性数据, 表明它可以导致明显稀薄的共构体表示 。