|
Математическая логика, алгебра и теория чисел
Дизъюнктивно-связные варианты проблемы выполнимости
В. Ю. Попов Ural Federal University, Lenin st., 51, 620083, Ekaterinburg, Russia
Аннотация:
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.
Ключевые слова:
satisfiability problem, computational complexity, NP-complete.
Поступила 27 марта 2024 г., опубликована 23 июня 2024 г.
Образец цитирования:
В. Ю. Попов, “Дизъюнктивно-связные варианты проблемы выполнимости”, Сиб. электрон. матем. изв., 21:1 (2024), 417–452
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1694 https://www.mathnet.ru/rus/semr/v21/i1/p417
|
|