algorithm - 两个 bool 表达式等价。合作NP？

Question

问题:我们需要判断两个 bool 公式是否具有相同的真值表

例如:(x1 v x2)∧(¬x1 v x3) 和 (¬x1 ∧ x2) v (x1 ∧ x3) 具有相同的值(x1, x2, x3) 的组合

我有几个想法:这个问题可能至少和重言式问题一样难。

证明“否”答案的正确性可能比证明"is"答案的正确性 (Co-NP) 更容易，但我不知道如何证明。另外，这里的证书是什么？是回答"is"还是“否”？

有什么想法吗？谢谢。

Answer 1

定义

假设 A == B 表示 A 和 B 在给定任何自由( bool )赋值的情况下始终计算为相同的 bool 表达式变量 x_i.

bool 表达式等价问题是，给定 A 和 B 来判断是否 A == B。

bool 重言式问题是，给定 A，对于自由( bool )变量 x_i 的所有可能赋值，A 是否计算为是的。

两个问题的等价性。

A==B 与 (A and B) or ((not A) and (not B)) 相同。因此，可以将 bool 等价问题的实例简化为重言式问题的实例。相反，给定 A，A == T 是重言式问题到 bool 表达式等价问题的化简。

所以 bool 表达式等价是 co-NP，实际上它是 co-NP 完全的，因为它等价于 bool 重言式的 co-NP 问题。

非等效证明。

您要求为互等价问题提供证明。这是 A != B 的证明。这只是自由变量 (x_i) 的赋值，因此两个 bool 公式的计算结果不同。您可以通过评估两个表达式在多项式时间内检查这一点。