On the Degree of Multivariate Polynomials over Fields of Characteristic 2

Marcel CRASMARU  

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

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


Summary: 
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.