2-Проблема выполнимости. Существует ли уникальное истинное назначение или нет.

Question

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

Answer 1

Федер (1994) описывает алгоритм эффективного составления списка всех решений для данного экземпляра 2-выполнимости..В статье также есть цитаты об алгоритмах подсчета количества назначений, но вам нужно попробовать перечислить только два назначения, что может оказаться более эффективным.