Geodesic
Two methods of estimation of Boolean bijunctive function weights
Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 4, pp. 125-142 
A. V. Tarasov. Two methods of estimation of Boolean bijunctive function weights. Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 4, pp. 125-142. http://geodesic.mathdoc.fr/item/MVK_2018_9_4_a6/
@article{MVK_2018_9_4_a6,
     author = {A. V. Tarasov},
     title = {Two methods of estimation of {Boolean} bijunctive function weights},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {125--142},
     year = {2018},
     volume = {9},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2018_9_4_a6/}
}
TY  - JOUR
AU  - A. V. Tarasov
TI  - Two methods of estimation of Boolean bijunctive function weights
JO  - Matematičeskie voprosy kriptografii
PY  - 2018
SP  - 125
EP  - 142
VL  - 9
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/MVK_2018_9_4_a6/
LA  - ru
ID  - MVK_2018_9_4_a6
ER  - 
%0 Journal Article
%A A. V. Tarasov
%T Two methods of estimation of Boolean bijunctive function weights
%J Matematičeskie voprosy kriptografii
%D 2018
%P 125-142
%V 9
%N 4
%U http://geodesic.mathdoc.fr/item/MVK_2018_9_4_a6/
%G ru
%F MVK_2018_9_4_a6

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

A problem of computation of the weight of function representable as 2-CNF (i. e. bijunctive function) belongs to the class of hard enumeration problems. Nevertheless there exist methods of upper and lower estimation of the weight of such functions. We consider two methods of estimation the weights: inclusionexclusion method and method using the monotone function on graph corresponding to the 2-CNF representing the bijunctive function. By means of these methods several polynomially computable estimates of the bijunctive functions weights are constructed.

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

[2] Tarasov A. V., “O svoistvakh funktsii, predstavimykh v vide 2-KNF”, Diskretnaya matematika, 13:4 (2001), 99–115 | DOI

[3] Gorshkov S. P., “O slozhnosti nakhozhdeniya chisla reshenii sistem bulevykh uravnenii”, Diskretnaya matematika, 6:1 (1996), 72–85 | DOI | Zbl

[4] Dahlöff V., Jonsson P., Wahlström M., “Counting models for 2SAT and 3SAT formulae”, Theor. Comput. Sci., 332:1–3 (2005), 265–291 | DOI | MR

[5] Dantsin E. Ya., “Algoritmika zadachi vypolnimosti”, Voprosy kibernetiki, 131 (1987), 7–21

[6] Gorshkov S. P., Tarasov A. V., “O vese bulevykh funktsii, predstavimykh v vide 2-KNF ili 3-KNF”, Matematicheskie voprosy kriptografii, 1:1 (2018), 5–26 | DOI

[7] Sachkov V. N., Kurs kombinatornogo analiza, NITs «Regulyarnaya i khaoticheskaya dinamika», M.–Izhevsk, 2013, 336 pp.

[8] Kharari F., Teoriya grafov, Mir, M., 1973, 300 pp.

[9] Zubkov A. M., “Neravenstva dlya raspredeleniya chisla odnovremenno proiskhodyaschikh sobytii”, Obozrenie prikl. i promyshl. matem., 1:4 (1994), 638–666 | Zbl

[10] Kofman A., Vvedenie v prikladnuyu kombinatoriku, Mir, M., 1975, 480 pp.

[11] Lovas L., Plammer M., Prikladnye zadachi teorii grafov. Teoriya parosochetanii v matematike, fizike i khimii, Mir, M., 1998, 653 pp.