Генерация решений на 2-SAT от существующего

Question

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

Answer 1

Я предполагаю, что это зависит от вашего определения "других решений", например, проблема оптимизации 2SAT (решение с минимальным количеством переменных, равным 1), является NP-Complete.

Если вам нужно какое-либо решение, и под "эффективным" вы подразумеваете полиномиальное время - вы можете поменять местами переменные в своем назначении с истина-> ложь и наоборот (один простой способ сделать это - добавить (x OR x) или за ложь (^x OR ^x)как пункт). Затем повторный запуск вашего решателя 2SAT даст вам другое решение, если оно существует. Вам нужно перезапустить свой решатель 2SAT самое большее n раз, где n - количество переменных, и поскольку ваш решатель 2SAT также имеет полиномиальное время, это решение выполняется за полиномиальное время.