Complexity of the satisfiability problem for multilinear forms over a finite field (Q682219)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Complexity of the satisfiability problem for multilinear forms over a finite field |
scientific article |
Statements
Complexity of the satisfiability problem for multilinear forms over a finite field (English)
0 references
14 February 2018
0 references
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.
0 references
function over finite field
0 references
linear function
0 references
multilinear form
0 references
satisfiability
0 references
\(NP\)-complete problem
0 references
polynomial algorithm
0 references
