我一直在阅读这篇文章，它尝试并解释了 max 2 sat 问题本质上是一个 3-sat 问题并且是 NP-hard 的。

但是，如果您看到这篇文章，我无法理解为什么，在ci满足之后，10 条中有 7 条满足，如果不满足，10 条中有 6 条满足。

有人可以简单地向我解释一下，并揭开这篇文章到底想表达什么的神秘面纱吗？本质上，我已经知道 max-2-sat 问题与 3 sat 问题相同。问题是我无法理解为什么。

更正式地说，我希望解决这个问题：

考虑如下描述的问题 MAX2SAT。

给定一个 2-CNF（连接范式）布尔表达式（有 m 个子句，n 个变量）和一个整数 k，确定是否有一个赋值至少满足总子句中的“k”个？计算 MAX2SAT 的复杂度等级（P 或 NP 或 NP Complete）并说明理由。

我正在查看以前的试卷，并且遇到了这个让我感到困惑的问题。

问题：

将子句给出的 Not-All-Equal 2-SAT 问题转换{x1, x2}, {x2, x3}, {x3, x4}, {x4, x5}, {x5, x1}为等效的 2-SAT 问题。（提示：2-SAT 问题包含 10 个子句）。

根据我的理解，这是否只是在每个子句中找到每个文字的否定？例如，{x1, x2} = {-x1, -x2}, 并且这是为每个子句完成的？这个对吗？

我正在解决 SCC 的两个可满足性问题，并且有一个关于拓扑排序的问题。我所基于的算法是以反向拓扑顺序处理 SCC，当它们全部连接时这很好。我的算法在这样的情况下被打破：

这使得图表看起来像这样：

此图中有两个源和两个汇，并且根据您从哪里开始有多个拓扑排序，因此有两个可能的最终节点。没有循环，因此每个节点都是一个 SCC。从源到接收器有多条路径，所以当我执行反向拓扑顺序时，我可以从接收器 x3 或接收器 !x2 开始。能给我正确答案的路径是从 !x2 开始，这将导致 1、-2、-3 或 -1、-2、-3，这两者都是解决方案。但如果我从 x3 开始，一个可能的结果是 -1、2、3，这不是解决方案。

所以当我查看我的两个接收器时，我如何从拓扑上决定哪个是最后一个？显然答案是！x2，但我试图弄清楚算法将如何确定它。我看到四个可能的想法：

• !x2 是最后一个，因为它有更多的节点通向它
• !x2 是最后一个，因为它位于较长路径的末端
• 在我开始处理任何东西之前设置每个接收器的真值
• 没有办法知道哪个是最后一个，所以创建所有可能的解决方案并测试它们中的每一个，看看它是否有效。

或者有什么关于拓扑排序 SCC 的问题吗？这是基于我在早期课程中通过强连通分量作业的算法，所以它不会完全错误。

假设我有一个带有 N 个输入和 1 个输出的黑盒电路。

我想固定 M 个输入的值并找到电路可满足的其余输入 (NM) 的值。如果我手动修复verilog RTL中的M个输入，并将其转换为CNF（使用abc），这会产生正确的结果吗？这是解决这类问题的正确方法吗？

如果是 3SAT 而不是一个子句有 2 个含义，我们可能会得到 12(3C2*2*2)在该结果图中找出强连通分量。这个使 3 SAT 成为 P 问题的陈述有什么问题？例如。

这是解决与 2SAT 相关的问题的代码。当输入值 n=200 000 时，此代码超出了 512 mB 的内存限制。我可以使用哪些技巧来减少内存使用？我已经尝试在主代码中分配向量 g 和 gt，然后在 dfs 和 dfs2 函数中我放置 g 和 gt 但这给了我时间限制问题。我如何优化这段代码？

2-SAT 问题，寻找变量的值

我正在使用这个解决方案来寻找给定公式的可满足性。（通过检查 SCC）。如果公式可满足，是否有任何有效的方法（在我的情况下，有效意味着不比多项式时间差）如何找到每个变量的值？

它不必在 C++ 中，我只是使用相同的算法。

涉及 SCC 的 2-SAT 的多项式时间算法告诉我们是否存在解决方案，也帮助我们生成问题的解决方案。但可以有不止一种解决方案。我想知道是否可以使用现有解决方案有效地生成其他解决方案？