Complexity of the satisfiability problem for multilinear forms over a finite field (Q682219)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6838067
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Complexity of the satisfiability problem for multilinear forms over a finite field |
scientific article; zbMATH DE number 6838067 |
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
0.9042921
0 references
0.8824379
0 references
0.8787874
0 references
0.87582225
0 references
0.8751933
0 references
0.87408996
0 references
0.87257934
0 references
