"Записки научных семинаров ПОМИ"
Том 475, стр. 122-136
Верхняя оценка для задачи выполнимости булевых схем с единственным выполняющим набором
А. А. Лялина
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург;
С.-Петербургский
государственный университет,
Университетский пр. 28,
Старый Петергоф,
198504 Санкт-Петербург, Россия
lyalina.albina@mail.ru
- Аннотация:
В данной статье рассматривается задача выполнимости булевых схем с не более чем одним выполняющим набором. Приводится алгоритм, решающий эту задачу за время $O(2^{.374589m})$, где $m$ обозначает число внутренних гейтов схемы. Для полноты изложения в статье также описан полученный Савиновым алгоритм, который решает общую задачу выполнимости булевой схемы за время $O(2^{.389667m})$.
Библ. -- 13 назв.
- Ключевые слова: задача выполнимости булевых схем, булевы схемы с единственным выполняющим набором, алгоритмы расщепления
[unique circuit SAT, circuit SAT, branching heuristics]
Полный текст(.pdf)