Complexity of the satisfiability problem for multilinear forms over a finite field (Q682219): Difference between revisions

The paper considers multilinear forms over finite fields, i.e., a product in which each factor is the sum of variables or elements of this field. The author shows that for each possible \(q \geq 3\), under which restrictions of the form of factors, the corresponding satisfiability problem for multilinear forms over a finite field of \(q\) elements can be solved using a polynomial algorithm. In addition, it is proved that this problem is \(NP\)-complete in all other cases.