2-проблема удовлетворенности - существует ли уникальное правдивое назначение или нет
У меня есть проблема, которая является расширением проблемы 2-SAT. В стандартной задаче 2-SAT мы можем найти любое из назначений истинности, которое зависит от порядка вершин, которые мы выбираем. Я хочу проверить, существует ли одно и только одно присвоение истинности (то есть только одна комбинация), для которого выражение выполнимо. Число литералов может быть 100000. Один из способов - найти все возможные назначения истинности, а затем сравнить их, если они различны. Но проблема для каждого сравнения, мне придется сравнить 100000 значений (без литералов). Есть ли эффективный способ?
1 ответ
Федер (1994) описывает алгоритм для эффективного перечисления всех решений для данного случая 2-удовлетворяемости. В статье также приводятся ссылки на алгоритмы для подсчета количества назначений, но вам нужно всего лишь попробовать перечислить два назначения, которые могут быть более эффективными.