Geodesic
Satisfiability in Boolean logic (SAT problem) is polynomial
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 14 (2021) no. 5, pp. 667-671.

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

We find a polynomial algorithm to solve SAT problem in Boolean Logic.
Keywords: Boolean logic, satisfiability problem, SAT algorithm. 
@article{JSFU_2021_14_5_a14,
     author = {Vladimir V. Rybakov},
     title = {Satisfiability in {Boolean} logic {(SAT} problem) is polynomial},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {667--671},
     publisher = {mathdoc},
     volume = {14},
     number = {5},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2021_14_5_a14/}
}
TY  - JOUR
AU  - Vladimir V. Rybakov
TI  - Satisfiability in Boolean logic (SAT problem) is polynomial
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2021
SP  - 667
EP  - 671
VL  - 14
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JSFU_2021_14_5_a14/
LA  - en
ID  - JSFU_2021_14_5_a14
ER  - 
%0 Journal Article
%A Vladimir V. Rybakov
%T Satisfiability in Boolean logic (SAT problem) is polynomial
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2021
%P 667-671
%V 14
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JSFU_2021_14_5_a14/
%G en
%F JSFU_2021_14_5_a14
Vladimir V. Rybakov. Satisfiability in Boolean logic (SAT problem) is polynomial. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 14 (2021) no. 5, pp. 667-671. http://geodesic.mathdoc.fr/item/JSFU_2021_14_5_a14/

[1] S. Cook, “The complexity of theorem proving procedures”, Proceedings of the Third Annual CAM Symposium on Theory of Computing, 1971, 151–158 | Zbl

[2] “A survey of Russian approaches to perebor (brute-force searches) algorithms”, Annals of the History of Computin, 6:4 (1984), 384–400 | DOI | Zbl

[3] B. Selman, D. Mitchell, H. Levesque, “Generating Hard Satisfiability Problems”, Artificial Intelligence, 81:1 (1996), 1729

[4] T.J. Schaefer, “The complexity of satisfiability problems”, Proceedings of the 10th Annual CAM Symposium on Theory of Computing (San Diego, California), 1978, 216–226 | Zbl

[5] V. Rybakov, “Admissible Rules in Pretabular Modal Logic”, Algebra and Logic, 20 (1981), 291–307 | DOI

[6] V. Rybakov, “Criterion for Admissibility for Rules in the Modal System S4 and Intuitionistic Logic”, Algebra and Logic, 23:5 (1984), 291–307 | DOI

[7] V.V. Rybakov, “Logical equations and admissible rules of inference with parameters in modal provability logics”, Studia Logica, 49:2 (1990), 215–239 | DOI | Zbl

[8] V.V. Rybakov, “Problems of substitution and admissibility in the modal system Grz and in intuitionistic propositional calculus”, Annals of Pure and Applied Logic, 50:1 (1990), 71–106 | DOI | Zbl

[9] V.V. Rybakov, Admissibility of Logical Inference Rules, Studies in Logic and the Foundations of Mathematics, 136, 1st Edition, Elsevier, 1997 | Zbl

[10] F. Massacci, L. Marraro, “Logical Cryptanalysis as a SAT Problem”, Journal of Automated Reasoning, 24:1 (2000), 165–203 | DOI | Zbl

[11] Marijn J. H. Heule, Hans van Maaren, “Look-Ahead Based SAT Solvers”, Handbook of Satisfiability, IOS Press, 2009, 155–184

[12] C. Moore, S. Mertens, The Nature of Computation, Oxford University Press, 2011 | Zbl