Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Grobner bases

JOURNAL OF ALGEBRA

卷:565

Article

Semaev, Igor¹  Tenti, Andrea¹ 

[1] Univ Bergen, Dept Informat, Bergen, Norway

关键词: Polynomial equation systems;    Finite fields;    Macaulay matrices;    Groebner bases;    Multisets;    Complexity;   

DOI  :  10.1016/j.jalgebra.2020.08.035

来源: Elsevier

【 摘 要 】

Grobner basis methods are used to solve systems of polynomial equations over finite fields, but their complexity is poorly understood. In this work an upper bound on the time complexity of constructing a Grobner basis according to a total degree monomial ordering and finding a solution of a system is proved. A key parameter in this estimate is the degree of regularity of the leading forms of the polynomials. Therefore, we provide an upper bound to the degree of regularity for a sufficiently overdetermined system of forms of the same degree over any finite field. The bound holds for almost all polynomial system and depends only on the number of variables, the number of polynomials, and the degree. Our results imply that almost all sufficiently overdetermined systems of polynomial equations of the same degree are solvable in polynomial time. (C) 2020 The Authors. Published by Elsevier Inc.

【 授权许可】

Free