On the Degree of Multivariate Polynomials over Fields of Characteristic 2
Marcel Crâşmaru · IEICE Transactions on Information and Systems · 2005
We show that a problem of deciding whether a formula for a multivariate polynomial of n variables over a finite field of characteristic 2 has degree n when reduced modulo a certain Boolean ideal belongs to P. When the formula is allowed to have succinct representations as sums of monomials, the problem becomes P--complete. 1