Complexity of the satisfiability problem for multilinear forms over a finite field |
| |
Authors: | S N Selezneva |
| |
Institution: | 1.Faculty of Computational Mathematics and Cybernetics,Moscow State University,Moscow,Russia |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|