Метод решения k-SAT-задачи сведением ее к задаче о покрытии

Abstract

Предложен алгоритм решения k-SAT-задачи в среднем за полиномиальное время и 3-SATзадачи за полиномиальное время. Предлагаемый метод позволяет существенно сократить время решения SAT-задач.

Запропоновано алгоритм розв’язку k-SAT-задачі в середньому за поліноміальний час і 3-SAT-задачі за поліноміальний час. Запропонований метод дозволяє істотно скоротити час розв’язку SAT-задач .

An algorithm for solving the k-SAT-problem for the average polynomial time and 3-SAT-problem for the polynomial time. The proposed method can significantly reduce the time to solve SAT-problems.