Title: Unsolvable Systems of Equations and Proof Complexity

This abstract discusses algebraic proof systems for the propositional calculus. We present recent results, current research directions, and open problems in this area.

1991 Mathematics Subject Classification: Primary 03F, 68Q, 68R05, 20C30, 14Q99

Keywords and Phrases: Systems of polynomial equations over finite fields, propositional proof complexity, lower bounds, Grobner bases.

Full text: dvi.gz 20 k, dvi 46 k, ps.gz 74 k.

Home Page of DOCUMENTA MATHEMATICA