Перечислите все решения проблемы SAT

11

Все известные мне решатели #SAT, например RelSat, C2D, возвращают только количество выполнимых экземпляров. Но я хочу знать каждый из этих случаев?

Существует ли такой решатель #SAT или как мне изменить имеющийся решатель #SAT, чтобы сделать это?

Спасибо.

lo.logic sat software ПБС
источник
7
Это часто называют «решением SAT для всех решений», но, кажется, не доступно с полки. Ссылки, которые я могу найти, говорят о модификациях MiniSAT и других решателей, обычно путем добавления блокирующих предложений, чтобы исключить решение, когда оно найдено. С другой стороны, большинство решателей ограничений поддерживают генерацию всех решений в качестве стандарта.
Андрас Саламон
Одним из подходов является конверсия CNF → DNF, для которой имеется много литературы
vzn 26.12.13

Ответы:

13

Вы ищете ALL-SAT или все решения SAT Solver. Это другая проблема от #SAT. Вам не нужно перечислять все решения для их подсчета.

Я не знаю инструмента, который решает вашу проблему, потому что люди добавляют эти алгоритмы поверх существующих решателей SAT, но, кажется, редко выпускают эти расширения. Ниже приведены две статьи, которые должны помочь вам в модификации решателя CDCL для реализации ALL-SAT.

SAT-решатель All-Solutions с эффективным использованием памяти и его применение к достижимости , О. Грумберг, А. Шустер, А. Ядгар, FMCAD 2004

Вот недавняя статья, опубликованная на arXiv.

Расширение современных SAT Solvers для перечисления всех моделей , Саид Джаббур, Лахдар Саис, Якуб Салихи, 2013

Вы можете попробовать связаться с этими авторами для их реализации.

Виджай Д
источник
Для второй статьи вам просто нужно нажать на первую версию v1, чтобы увидеть ее.
Тайфун Pay
Эта недавняя статья кажется родственной: homes.cs.washington.edu/~sudeepa/UAI2013-ModelCounting.pdf
Каве
1
@Kaveh, я полагаю, что ОП запрашивает решатель ALLSAT или способ превратить решатель #SAT в решатель ALLSAT. Это статья о нижних границах для #SAT. Я не уверен, что это помогает ОП.
Виджай Д
2

Я нашел более свежую (2014 г.) статью о All-SAT на конференции VLSI, так что она определенно ориентирована на практическую сторону (что, похоже, согласуется с вопросом OP здесь, хотя и с cstheory.SE в целом):

  • «All-SAT с использованием положений о минимальной блокировке». Автор: Инлей Ю., Прамод Субраманян, Нестан Цискаридзе, Шарад Малик, VLSI Design 2014. doi: 10.1109 / VLSID.2014.22 .

Для тех, у кого нет подписки IEEE, есть бесплатная копия на веб-странице Субраманяна в Принстоне . (Он использует файлообменный сервис для хранения / распространения копий своих статей, и я не уверен, насколько стабильны эти URL-адреса, отсюда и эта обходная ссылка.)

Суть этой статьи выглядит так:

Наш вклад, алгоритм Non-Disjoint-Dec, генерирует чрезвычайно короткие блокирующие предложения, которые не содержат ни одной из подразумеваемых переменных в решателе. Обратите внимание, что обычно подразумевается большинство переменных в удовлетворительной минуте. Короткие условия блокировки очень полезны для производительности решателя, что продемонстрировано оценкой.

Их реализация основана на MiniSat. Исходный код для их расширения, похоже, не является общедоступным. Увы, это, кажется, привычка в области All-SAT, поэтому статьи в этой области, которые содержат экспериментальные результаты, просто устанавливают какой-то более-менее простой алгоритм, который можно превзойти, и редко могут напрямую сравниваться (с точки зрения экспериментального результаты) с любым другим опубликованным алгоритмом для All-SAT. Бумага Jabbour et al. упомянутый Виджаем D тоже относится к этому виду.

Как я не вижу в упомянутом другом ответе (но только в комментарии Андраса Саламона), [довольно популярный] метод блокирующих предложений был представлен в:

шипение
источник