Geodesic
Schaefer classes, Post classes and Galois connections
Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 1, pp. 81-107 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

An universal algebra on the set of Boolean functions with operations of function conjunction, projection with respect to a variable and transposition of variables is considered. The structure of functions constituting subalgebras of this algebra are described. It is shown that there exists a Galois connection between subalgebras of the algebra considered and subalgebras of iterative Post algebra; this connection links our results with known papers on Post classes. 
@article{MVK_2015_6_1_a3,
     author = {V. S. Litvinenko and A. V. Tarasov},
     title = {Schaefer classes, {Post} classes and {Galois} connections},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {81--107},
     year = {2015},
     volume = {6},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2015_6_1_a3/}
}
TY  - JOUR
AU  - V. S. Litvinenko
AU  - A. V. Tarasov
TI  - Schaefer classes, Post classes and Galois connections
JO  - Matematičeskie voprosy kriptografii
PY  - 2015
SP  - 81
EP  - 107
VL  - 6
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MVK_2015_6_1_a3/
LA  - ru
ID  - MVK_2015_6_1_a3
ER  - 
%0 Journal Article
%A V. S. Litvinenko
%A A. V. Tarasov
%T Schaefer classes, Post classes and Galois connections
%J Matematičeskie voprosy kriptografii
%D 2015
%P 81-107
%V 6
%N 1
%U http://geodesic.mathdoc.fr/item/MVK_2015_6_1_a3/
%G ru
%F MVK_2015_6_1_a3
V. S. Litvinenko; A. V. Tarasov. Schaefer classes, Post classes and Galois connections. Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 1, pp. 81-107. http://geodesic.mathdoc.fr/item/MVK_2015_6_1_a3/

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

[2] Gorshkov S. P., “Primenenie teorii NP-polnykh zadach dlya otsenki slozhnosti resheniya sistem bulevykh uravnenii”, Obozr. prikl. i promyshl. matem., ser. diskr. matem., 2:3 (1995), 325–398

[3] Gorshkov S. P., “O peresecheniyakh klassov multiaffinnykh, biyunktivnykh, slabo polozhitelnykh i slabo otritsatelnykh bulevykh funktsii”, Obozr. prikl. i promyshl. matem., ser. diskr. matem., 4:2 (1997), 238–259

[4] Creighnou N., Khanna S., Sudan M., Complexity classifications of Boolean constraint satisfaction problems, SIAM Press, Philadelphia, USA, 2001 | MR

[5] Tarasov A. V., “Obobschenie kriteriya biyunktivnostiShefera”, Diskretnaya matematika, 24:2 (2012), 92–99 | DOI | MR

[6] Sachkov V. N., “Razbieniya s pogloscheniyami i protivorechivye razbieniya mnozhestv”, Trudy po diskretnoi matematike, 4, Fizmatlit, M., 2001, 201–222

[7] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1979 | MR

[8] Bodnarchuk V. G., Kaluzhnin L. A., Kotov V. N., Romov B. A., “Teoriya Galua dlya klassov Posta. I”, Kibernetika, 1969, no. 3, 1–10 | Zbl

[9] Marchenkov S. S., “Invarianty klassov Posta”, Fundam. i prikl. matem., 4:4 (1998), 1385–1404 | MR | Zbl

[10] Marchenkov S. S., Zamknutye klassy bulevykh funktsii, Fizmatlit, M., 2001, 126 pp. | MR

[11] Kon P., Universalnaya algebra, Mir, M., 1968 | MR

[12] Ore O., Teoriya grafov, Librokom, M., 2008

[13] Parvatov N. G., “Sootvetstvie Galua dlya zamknutykh klassov diskretnykh funktsii”, Prikl. diskr. matem., 2010, no. 2(8), 10–15

[14] Yablonskii S. V., Gavrilov G. P., Kudryavtsev V. B., Funktsii algebry logiki i klassy Posta, Nauka, M., 1966, 119 pp. | MR