On the Degree of Multivariate Polynomials over Fields of Characteristic 2


IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.1   pp.103-108
Publication Date: 2005/01/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.1.103
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computation and Computational Models
degree of multivariate polynomials,  finite field of characteristic 2,  parity P-complete,  Hamilton path,  

Full Text: PDF(140.6KB)
>>Buy this Article

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.