Complexity of the satisfiability problem for multilinear forms over a finite field
Светлана Николаевна Селезнева · Moscow University Computational Mathematics and Cybernetics · 2017
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.