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

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q285505
RedirectionBot (talk | contribs)
Changed an Item
Property / author
 
Property / author: Svetlana N. Selezneva / rank
 
Normal rank

Revision as of 15:43, 12 February 2024

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

    Identifiers