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

• Опубліковано в: : Электронное моделирование
• Дата: 2015
• Автори: Листровой, С.В., Сидоренко, А.В.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2015
• Теми: Математическое моделирование и вычислительные методы
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/101162
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Метод решения k-SAT-задачи сведением ее к задаче о покрытии / С.В. Листровой, А.В. Сидоренко // Электронное моделирование. — 2015. — Т. 37, № 5. — С. 17-34. — Бібліогр.: 4 назв. — рос.

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