2-Проблема выполнимости. Существует ли уникальное истинное назначение или нет.
-
13-09-2019 - |
Вопрос
У меня проблема, которая является продолжением проблемы 2-SAT.В стандартной задаче 2-SAT мы можем найти любое истинностное назначение, которое зависит от выбранного нами порядка вершин.Я хочу проверить, существует ли одно и только одно истинное назначение (т.е. только одна комбинация), для которого выражение является выполнимым.Количество литералов может быть 100000.Один из способов — найти все возможные истинностные назначения, а затем сравнить их, если они различны.Но проблема в том, что для каждого сравнения мне придется сравнивать 100 000 значений (без литералов).Есть ли какой-нибудь эффективный способ?
Решение
Федер (1994) описывает алгоритм эффективного составления списка всех решений для данного экземпляра 2-выполнимости..В статье также есть цитаты об алгоритмах подсчета количества назначений, но вам нужно попробовать перечислить только два назначения, что может оказаться более эффективным.