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