On the degree of ideal membership proofs from uniform families of polynomials over a finite field

zbMath0984.03044MaRDI QIDQ5954264

Jan Krajíček

Publication date: 17 February 2002

Published in: Illinois Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

lower bound; ideal membership; modular counting principle; polynomial calculus; polynomials over a finite prime field; proof degree; tabloid moduli

Mathematics Subject Classification ID

12E12: Equations in general fields

13L05: Applications of logic to commutative algebra

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

12L12: Model theory of fields

03F20: Complexity of proofs

Related Items

Linear gaps between degrees for the polynomial calculus modulo distinct primes, Bounds in the theory of finite covers, A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems]