On the degree of ideal membership proofs from uniform families of polynomials over a finite field
From MaRDI portal
Publication:5954264
zbMath0984.03044MaRDI QIDQ5954264
Publication date: 17 February 2002
Published in: Illinois Journal of Mathematics (Search for Journal in Brave)
lower bound; ideal membership; modular counting principle; polynomial calculus; polynomials over a finite prime field; proof degree; tabloid moduli
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]