Geodesic
On the weights of Boolean functions representable by $2$-CNF or $3$-CNF
Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 1, pp. 5-26 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Sets of possible values of weights of bijunctive Boolean functions ($2$-CNF) are found. For Boolean functions having all variables as essential ones we describe: sets of bijunctive functions with weight close (but not equal) to the maximal value and sets of functions of maximal weight represented as $3$-CNF. A hypothesis on the maximal weight of functions representable as $k$-CNF ($k \geqslant 4$) and having all variables as essential ones is formulated. Some sets of balanced Boolean functions representable as $k$-CNF are described. 
@article{MVK_2018_9_1_a0,
     author = {S. P. Gorshkov and A. V. Tarasov},
     title = {On the weights of {Boolean} functions representable by $2${-CNF} or $3${-CNF}},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {5--26},
     year = {2018},
     volume = {9},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2018_9_1_a0/}
}
TY  - JOUR
AU  - S. P. Gorshkov
AU  - A. V. Tarasov
TI  - On the weights of Boolean functions representable by $2$-CNF or $3$-CNF
JO  - Matematičeskie voprosy kriptografii
PY  - 2018
SP  - 5
EP  - 26
VL  - 9
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MVK_2018_9_1_a0/
LA  - ru
ID  - MVK_2018_9_1_a0
ER  - 
%0 Journal Article
%A S. P. Gorshkov
%A A. V. Tarasov
%T On the weights of Boolean functions representable by $2$-CNF or $3$-CNF
%J Matematičeskie voprosy kriptografii
%D 2018
%P 5-26
%V 9
%N 1
%U http://geodesic.mathdoc.fr/item/MVK_2018_9_1_a0/
%G ru
%F MVK_2018_9_1_a0
S. P. Gorshkov; A. V. Tarasov. On the weights of Boolean functions representable by $2$-CNF or $3$-CNF. Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 1, pp. 5-26. http://geodesic.mathdoc.fr/item/MVK_2018_9_1_a0/

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

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

[3] Monien B., Speckenmeyer E., “Solving satisfiability in less than $2^n$ steps”, Discr. Appl. Math., 1985, no. 10, 287–295 | DOI | MR | Zbl

[4] Dantsin E. Ya., “Algoritmika zadachi vypolnimosti”, Problema sokrascheniya perebora, Voprosy kibernetiki, 131, 1987, 7–29

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

[6] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp.

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