Complexity of the satisfiability problem for multilinear forms over a finite field

Abstract

Multilinear forms over finite fields are considered. Multilinear forms over a field are products in which each factor is the sum of variables or elements of this field. Each multilinear form defines a function over this field. A multilinear form is called satisfiable if it represents a nonzero function. We show the N P-completeness of the satisfiability recognition problem for multilinear forms over each finite field of q elements for q ≥ 3. A theorem is proved that distinguishes cases of polynomiality and NP-completeness of the satisfiability recognition problem for multilinear fields for each possible q ≥ 3.