Tseitin's tautologies and lower bounds for Nullstellensatz proofs

被引：23

作者：

Grigoriev, D ^{[1
]}

机构：

[1] Penn State Univ, Dept Math & Comp Sci, University Pk, PA 16802 USA

来源：

39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1998年

关键词：

D O I：

10.1109/SFCS.1998.743515

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We use the known linear lower bound far Tseitin's tautologies far establishing linear lower bounds on the degree of Nullstellensatz proofs (in the usual boolean setting) for explicitly constructed systems of polynomials of a constant (in our construction 6) degree. Tt holds over any field of characteristic distinct from 2. Previously, a linear lower bound was proved [14] for an explicitly constructed system of polynomials of a logarithmic degree.

引用

页码：648 / 652

页数：3