Geodesic
On properties of multiaffine predicates on a finite set
Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 141-152.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider predicates on a finite set that are invariant with respect to an affine operation $f_G$, where $G$ is some Abelian group. Such predicates are said to be multiaffine for the group $G$. Special attention is paid to predicates that are affine for a group $G_q$ of addition modulo $q = p^s$, where $p$ is a prime number and $s \geqslant 1$. We establish the predicate multiaffinity criterion for a group $G_q$. Then we introduce disjunctive normal forms (DNF) for predicates on a finite set and obtain properties of DNFs of predicates that are multiaffine for a group $G_q$. Finally we show how these properties can be used to design a polynomial algorithm that decides satisfiability of a system of predicates which are multiaffine for a group $G_q$, if predicates are specified by DNF.
Keywords: predicate on a finite set, function on a finite set, affine operation, multiaffinity, disjunctive normal form, algorithm, complexity, polynomial algorithm. 
@article{DM_2021_33_4_a11,
     author = {S. N. Selezneva},
     title = {On properties of multiaffine predicates on a finite set},
     journal = {Diskretnaya Matematika},
     pages = {141--152},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2021_33_4_a11/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - On properties of multiaffine predicates on a finite set
JO  - Diskretnaya Matematika
PY  - 2021
SP  - 141
EP  - 152
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2021_33_4_a11/
LA  - ru
ID  - DM_2021_33_4_a11
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T On properties of multiaffine predicates on a finite set
%J Diskretnaya Matematika
%D 2021
%P 141-152
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2021_33_4_a11/
%G ru
%F DM_2021_33_4_a11
S. N. Selezneva. On properties of multiaffine predicates on a finite set. Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 141-152. http://geodesic.mathdoc.fr/item/DM_2021_33_4_a11/

[1] Schaefer T., “Complexity of satisfiability problems”, Proc. 10th ACM Symp. Theory of Computing, ACM Press, 1978, 216–226 | Zbl

[2] Jeavons P., Coher D., Gyssens M., “Closure properties of constraints”, J. ACM, 44 (1997), 527–548 | DOI | Zbl

[3] Gorshkov S. P., “O slozhnosti raspoznavaniya multiaffinnosti, biyunktivnosti, slaboi polozhitelnosti i slaboi otritsatelnosti”, Obozr. promyshl. i prikl. matem., 4:2 (1997), 216–237

[4] Selezneva S. N., “O multiaffinnykh mnogochlenakh nad konechnym polem”, Diskretnaya matematika, 32:3 (2020), 85–97

[5] Selezneva S. N., “O biyunktivnykh predikatakh nad konechnym mnozhestvom”, Diskretnaya matematika, no. 4, 130–142 ; Selezneva S.N., “On bijunctive predicates over a finite set”, Discrete Math. Appl., 29:1 (2019), 49–58 | DOI | Zbl | DOI

[6] Selezneva S. N., “Ob $m$-yunktivnykh predikatakh na konechnom mnozhestve”, Diskretn. analiz i issled. oper., 26:3 (2019), 46–59 | DOI | Zbl

[7] Selezneva S. N., “O slabo polozhitelnykh predikatakh nad konechnym mnozhestvom”, Diskretnaya matematika, 30:3 (2018), 127–140 ; Selezneva S. N., “On weak positive predicates over a finite set”, Discrete Math. Appl., 30:3 (2020), 203–213 | DOI | MR | DOI | Zbl

[8] Tyrtyshnikov E. E., Osnovy algebry, Fizmatlit, M., 2017, 464 pp.

[9] Goldmann M., Russell A., “The complexity of solving equations over finite groups”, Inf. and Comput., 178 (2002), 253–262 | DOI | Zbl

[10] Vasilenko O. N., Teoretiko-chislovye algoritmy v kriptografii, MTsNMO, M., 2003, 328 pp.

[11] Elizarov V. P., “Sistemy lineinykh uravnenii nad konechnymi koltsami”, Trudy po diskretnoi matematike, 6 (2002), 31–47

[12] Elizarov V. P., “Ob algoritme posledovatelnogo resheniya sistemy lineinykh uravnenii nad koltsom vychetov”, Trudy po diskretnoi matematike, 11:2 (2008), 31–42

[13] Elizarov V. P., Konechnye koltsa, Gelios ARV, M., 2006, 303 pp.

[14] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Trudy Matem. in-ta im. V. A. Steklova AN SSSR, 51 (1958), 5–142 | Zbl

[15] Gorshkov S. P., Tarasov A. V., Slozhnost resheniya sistem bulevykh uravnenii, Kurs, M., 2017, 192 pp.