Geodesic
Clause-connected versions of the satisfiability problem
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 417-452

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

The satisfiability problem is one of the most famous computationally hard algorithmic problems. It is well known that the satisfiability problem remains hard even in the restricted version in which Boolean formulas in conjunctive normal form with exactly three distinct literals per clause. However, the problem can be solved in polynomial time for Boolean formulas with exactly two distinct literals per clause. Narrowing the gap between the problems is of fundamental interest. Therefore, it is natural to analyze the complexity of some restricted versions of the satisfiability problem. In this paper, we prove hardness of some clause-connected versions of the satisfiability problem.
Keywords: satisfiability problem, computational complexity, NP-complete. 
@article{SEMR_2024_21_1_a12,
     author = {V. Yu. Popov},
     title = {Clause-connected versions of the satisfiability problem},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {417--452},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a12/}
}
TY  - JOUR
AU  - V. Yu. Popov
TI  - Clause-connected versions of the satisfiability problem
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 417
EP  - 452
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a12/
LA  - ru
ID  - SEMR_2024_21_1_a12
ER  - 
%0 Journal Article
%A V. Yu. Popov
%T Clause-connected versions of the satisfiability problem
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 417-452
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a12/
%G ru
%F SEMR_2024_21_1_a12
V. Yu. Popov. Clause-connected versions of the satisfiability problem. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 417-452. http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a12/