论文标题
Blackbox激进会员资格，无效和超越学位的特殊案例算法
Special-case Algorithms for Blackbox Radical Membership, Nullstellensatz and Transcendence Degree
论文作者
论文摘要
激进的会员资格测试以及希尔伯特的无效的特殊情况（HN）是一个基本计算代数问题。它是NP-HARD；并且由于有效的零史塔兹范围，并且具有著名的Pspace算法。我们确定了这些问题的有用情况，即可以给出的实用算法和改进的界限，当输入多项式的超越程度$ r $小于变量$ n $的数量时。如果$ d $是输入多项式上的学位，那么我们在$ d^r $时间左右解决了激进的会员资格（即使输入多项式是黑框）。先前的最佳是$> d^n $时间（始终，$ d^n \ ge d^r $）。此外，当$ r \ ll n $时，我们会显着提高有效的零史塔兹学位。从结构上讲，我们的证明表明，这些问题减少了$ r+1 $的超越程度$ \ ge r $的情况。此输入实例（对应于无或唯一的歼灭器）是HN硬度的核心。我们的证明方法调用基本代数几何。
Radical membership testing, and the special case of Hilbert's Nullstellensatz (HN), is a fundamental computational algebra problem. It is NP-hard; and has a famous PSPACE algorithm due to effective Nullstellensatz bounds. We identify a useful case of these problems where practical algorithms, and improved bounds, could be given, when the transcendence degree $r$ of the input polynomials is smaller than the number of variables $n$. If $d$ is the degree bound on the input polynomials, then we solve radical membership (even if input polynomials are blackboxes) in around $d^r$ time. The prior best was $> d^n$ time (always, $d^n\ge d^r$). Also, we significantly improve effective Nullstellensatz degree-bound, when $r\ll n$. Structurally, our proof shows that these problems reduce to the case of $r+1$ polynomials of transcendence degree $\ge r$. This input instance (corresponding to none or a unique annihilator) is at the core of HN's hardness. Our proof methods invoke basic algebraic-geometry.
