我阅读了许多用于查找 2-SAT 问题的算法，即给定的表达式是否可满足，可以在多项式时间内求解。示例（算法）。
对于Krom 的过程（维基百科），我构建了一个图，从中我可以轻松地验证它在多项式时间内的可满足性。
现在，我想找到这个表达式的解决方案是令人满意的。
我是这样想的（验证它）：首先我取任何形成强连通分量的表达式文字，比如 x，并将值赋值为 0。然后根据算法，存在边（x！-> y）。因此 y 不能为 0。（因为 1 -> 0 为假）并且如果可能，类似地继续。
否则取 x=0，然后只能选择 y=1，然后类似地继续获取任何 1 个可满足的实例。
现在，是否有任何可行的解决方案可以在多项式时间内找到其中任何一个
- 给出表达式可满足的所有可能解。
- 或者这个表达式对于总 k 字面量 = 1 的输入是否可以满足。
- 或者有多少最小数量的文字具有值 1 才能满足表达式。
对于这类问题，我没有得到任何多项式算法。