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

• Published in: Электронное моделирование
• Date: 2015
• Main Authors: Листровой, С.В., Сидоренко, А.В.
• Format: Article
• Language: Russian
• Published: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2015
• Subjects: Математическое моделирование и вычислительные методы
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/101162
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Метод решения k-SAT-задачи сведением ее к задаче о покрытии / С.В. Листровой, А.В. Сидоренко // Электронное моделирование. — 2015. — Т. 37, № 5. — С. 17-34. — Бібліогр.: 4 назв. — рос.

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