Полиномиальный алгоритм для алгоритма, связанного с 2-SAT

Question

Я прочитал много алгоритмов для нахождения задачи 2-SAT, т.е. данное выражение выполнимо или нет, которое может быть решено за полиномиальное время. пример ( алгоритм).
Для процедуры Крома( Википедия) я строю граф, из которого я могу легко проверить его выполнимость за полиномиальное время.
Теперь я хочу найти решение этого выражения для удовлетворения.
Я думаю вот так (проверьте это): сначала я беру любой литерал выражения, который образует сильный связный компонент, скажем, x, и присваиваю значение как 0. Затем, согласно алгоритму, существует ребро ( x! -> y). следовательно, у не может быть 0. (так как 1 -> 0 ложно) и аналогично, если возможно.
В противном случае возьмите x=0 и затем выберите только y=1, и аналогичным образом продолжите, чтобы получить любой 1 экземпляр, для которого он выполним.

Теперь, есть ли возможное решение найти что- либо из этого за полиномиальное время

• дать все возможные решения, для которых выражение выполнимо.
• Или это выражение выполнимо для ввода, имеющего общее число литералов = 1.
• Или сколько минимальных чисел литералов имеют значение 1 для выражения, чтобы быть выполнимым.

Я не получаю никакого полиномиального алгоритма для этого типа вопросов.

Answer 1

дать все возможные решения, для которых выполнимо выражение

Нет, потому что их может быть экспоненциально много.

Или это выражение выполнимо для ввода, имеющего всего k литералов = 1

Нет, потому что, если бы это было легко, то так же было бы взвешенная 2-выполнимость (NP-сложная).

Или сколько минимальных чисел литералов имеют значение 1 для выражения, чтобы быть выполнимым

Это взвешенный 2-SAT.