克罗姆公式的等价性易丧传？

Question

假设我有两个 kromformulas $ \ psi_1，\psi_2 $ 。Krom公式是CNF中的命题式，每个条款都有2个文字。每个文字都可以否定或不受欢迎。换句话说， $ \ psi_1，\ psi_2 $ 是2-CNF公式。例如：

$（x_1 \ vee \ neg x_2）\ land（\ neg x_2 \ vee x_3）\ land（x_3 \ vee x_4）$

我想决定 $ \ psi_1，\ psi_2 $ 是逻辑上等效的，即 $ \ psi_1 \ leftrightarrow\ psi_2 $ 。等效，我想测试<跨度类=“math-container”> $ f=（\ psi_1 \ vee \ neg \ psi_2）\ wedge（\ neg \ psi_1 \ vee \ psi_2）$ $ x_1，\ dots，x_n $ 的所有分配。

这个问题是易旧的吗？

Answer 1

是，可以在多项式时间（实际上，在二次时间中）检查等价。

我将描述如何测试 $ \ psi_1 \ lor \ neg \ psi_2 $ 为所有作业都是如此。您可以对 $ \ neg \ psi_1 \ lor \ psi_2 $ 来做同样的事情，并用它来测试 $ f $ 是一个是一个ta模式，即是否 $ \ psi_1，\ psi_2 $ 逻辑上等效。

我会通过检查 $ \ psi_1 \ lor \ neg \ psi_2 $ 对于任何分配来说是false来执行此操作，或者换句话说，是否 $ \ neg（\ psi_1 \ lor \ psi_2）$ 是满意的。注意

$$ \ neg（\ psi_1 \ lor \ neg \ psi_2）=neg \ psi_1 \ land \ psi_2，$$

所以它足以测试 $ \ neg \ psi_1 \ land \ psi_2 $ 其中 $ \ psi_1，\ psi_2 $ 是KROM（2-CNF）公式。

假设 $ \ psi_1= c_1 \ land \ cdots \ land c_k $ 其中 $ c_i $ 是 $ i $ th子句在 $ \ psi_1 $ 中。然后是

$$ \ neg \ psi_1=（\ neg c_1）\ lor \ cdots \ lor（\ neg c_k）。$$

因此

$$ \ begin {align *} \ neg \ psi_1 \ land \ psi_2＆=（（\ neg c_1）\ lor \ cdots \ lor（\ neg c_k））\ land \ psi_2 \\ ＆=（\ neg c_1 \ land \ psi_2）\ lor \ cdots \ lor（\ neg c_k \ land \ psi_2）。 \结束{align *} $$

现在， $ \ neg \ psi_1 \ land \ psi_2 $ 是满足的iff $ \ neg c_i \ land \ psi_2 $ 对于某些 $ i $ ，对于“math-container”是满意的。所以，我们可以迭代 $ i $ 并测试每个 $ \ neg c_i \ land \ psi_2 $ 如果其中任何一个是满足的，那么 $ \ neg \ psi_1 \ lor \ psi_2 $ 是满足的， $ f $ 不是Tautology和 $ \ Psi_1，\ PSI_2 $ 没有逻辑等效。

如何测试 $ \ neg c_i \ land \ psi_2 $ 的满足性？嗯， $ c_i $ 具有 $（\ ell_1 \ lor \ ell_2）$ 其中 $ \ ell_1，\ ell_2 $ 是两个文字，所以 $ \ neg c_i \ land \ psi_2 $ 具有表单<跨越类=“math-container”> $ \ neg \ ell_1 \ land \ neg \ ell_2 \ land \ psi_2 $ 。这也是KROM（2-CNF）公式，因此您可以使用标准多项式算法测试其可靠性。您执行此类测试的线性数量，因此总运行时间是多项式。事实上，它是二次的，因为可以在线性时间进行测试可满足性。

Answer 2

召回使用强连接组件的2-sat解决方案：我们用顶点构建一个图 $ x_1，\ ldots，x_n，\ lnot x_1，\ ldots，\ lnot x_n $ < / span>，我们替换每个子句 $ x_i \ lor x_j $ 使用边缘 $ \ lnot x_i \ to x_j $ < / span>和 $ \ lnot x_j \到x_i $ 。来自这里

为了满足公式，它是必要的并且足以分配顶点，以便图表中没有矛盾（无边缘 $ true \ to false $ ）。我们将使用这些图表进行等价检查。

1. 我们构建这些图形 $ g_1 $ 和 $ g_2 $ 两个公式 $ f_1 $ 和 $ f_2 $ 。
2. 如果有一个循环 $ x_i \ leadsto \ lnot x_i \ leadsto x_i $ 在图中，则其公式没有解决方案。我们检查两种公式是否是可溶性/无法解决的。
3. 如果存在一个表单 $ x_i \ leadsto \ lnot x_i $ （类似于案例 $ \ lnot x_i \ leadsto x_i $ ），我们知道要满足公式，我们必须选择 $ x_i $ 为false（否则我们有一个矛盾）。我们记得这个选择。使用图形，我们可以为来自 $ \ lnot x_i $ （它们必须为真）的所有顶点分配值。再次，检查两种公式是否完全相同的决定。
4. 从图表中删除所有已知顶点的所有边缘。
现在， $ f_1 $ 和 $ f_2 $ 等效 $ \ iff $ 下行中的剩余图表是等效的：对于任何 $ v_1，v_2 $ path $ v_1 \ leadsto v_2 $ 存在于 $ g_1 $ iff它存在于 $ g_2 $ 。这可以在大多数 $ o（| v | \ cdot | e |）$ 时间（从每个顶点运行dfs并检查它是否访问过的两个图表的顶点）。也许它可以更快地完成。

证明：

$ \ leftarrow $ ：明显，由于在图形的传递关闭之后，我们将在两个公式中具有相同的含义。

$ \ lightarrow $ ：通过矛盾。 WLOG我们假设存在一个路径 $ v_1 \ leadsto v_2 $ 在 $ g_1 $ 中没有存在于 $ g_2 $ 中。这意味着赋值 $ v_1：= true $ ， $ v_2：= false $ 在 $ f_2 $ （因为没有路径 $ v_1 \ leadsto v_2 $ ），但在 $ f_1 $ 。

即，以下赋值满足 $ f_2 $ ：

• $ true $ 从 $ v_1 $ 。
• $ false $ 从所有顶点到达 $ v_2 $ 。
• 从图表中删除所有已知的顶点（上面提到的互补品）。所有剩余顶点都会创建连接组件。我们在 $ true $ 中彩色连接组件，以及与其补充的连接组件 - 在 $ false $ 中（见下面的注意）。

此分配没有矛盾，因为没有边缘 $ u \ to v $ 形式 $ true \ false $ ：

• 如果 $ u $ 属于满族的组件 $ true $ ，那么如此<跨越类=“math-container”> $ v $ 也必须是真的。
否则
• 否则，意味着 $ u $ 可从 $ v_1 $ ，因此 $ V $ 也可以从 $ v_1 $ ，并且必须是真的。 $ \ blacksquare $

技术说明：对于每个变量 $ x_i $ 有两个顶点：

一个类=“math-container”> $ v_i $ 和 $ \ lnot v_i $ - 并且一个可能想知道它是否会导致一些问题作业。答案是在步骤4）之后， $ v_i $ 和 $ \ lnot v_i $ 将位于两个不同的组件（而且，它们是对称的： $ u \ to v $ 在一个组件中意味着 $ \ lnot u \ to \lnot v $ 另一个）。因此，无论我们在一个组件中为 $ u $ 所做的任何决定，我们都可以对 $ \ lnotu $来表示相反的决定在另一个中。