2-SAT相关算法的多项式算法

Question

我读了很多寻找 2-SAT 问题的算法，即给定的表达式是否可满足，可以在多项式时间内解决。示例(algorithm).
对于 Krom 的过程(Wikipedia)，我构造了一个图，从中我可以很容易地验证它在多项式时间内的可满足性。
现在，我想找到可满足此表达式的解决方案。
我是这样想的（验证一下）：首先我采用任何形成强连通分量的表达式文字 x，并将值赋值为 0。然后根据算法，存在边（x！-> y）。因此 y 不能为 0。（因为 1 -> 0 为假）并且如果可能的话类似地进行。
否则取 x=0 然后只有选择 y=1 并类似地继续获得它可满足的任何 1 个实例。

现在，在多项式时间

中找到任何一个的可行解

• 给出表达式可满足的所有可能的解决方案。
• 或者对于总 k 个文字 = 1 的输入，此表达式是否可满足。
• 或者至少有多少文字的值为 1 才能满足表达式。

对于此类问题，我没有得到任何多项式算法。

Answer 1

give all possible solutions for which expression is satisfiable

不，因为可以有指数级的多。

Or is this expression is satisfiable for input having total k literals = 1

不，因为如果这很容易，那么加权 2-可满足性（NP-hard）也会如此。

Or how many minimum number of literals have value 1 for expression to be satisfiable

这个 是 加权 2-SAT。