Groebner basis in Boolean rings is not polynomial-space

2015/02/25 by Mark van Hoeij, van Hoeij, Mark
Computer Science · #FOS: Computer and information sciences #Symbolic Computation (cs.SC) #cs.SC

paper · pdf · doi:10.48550/arxiv.1502.07220

3 pages

arxiv created 2015/02/26 · arxiv updated 2015/02/27

Abstract

We give an example where the number of elements of a Groebner basis in a Boolean ring is not polynomially bounded in terms of the bitsize and degrees of the input.

Related

• New developments in the theory of Groebner bases and applications to formal verification
• Fast Gröbner Basis Computation for Boolean Polynomials
• Groebner bases for the polynomial ring with infinite variables and their applications
• A Systematic Study of Groebner Basis Methods
• Nonlinearity of Boolean functions: an algorithmic approach based on multivariate polynomials