QBFS中的通用量词

Question

我一直在努力减少tQBF语言，并陷入困境，几乎肯定不是真的（或者，如果是真的，我缺少与它相关的重要计算成本）尊重简化TQBF实例。

为了简单起见，让我们来限制Prenex正常形式和CNF中的TQBF实例，没有自由变量。我的假设（我强烈怀疑是错误的，但已经无法找到一个反例）是，如果才能且才能删除来自句子的普遍量化变量的所有实例的TQBF，则此类TQBF是满意的。例如，拍摄以下实例：

$ \存在a \ forall b \存在c \ forall d $ $ \ psi（a，b，c ，d）$

$ \ psi（a，b，c，d）=（\ neg a \ vee b \ vee c）\ wedge（\ neg b \ vee \ neg c \ Vee d）\ wedge（a \ vee c \ vee \ neg d）$

首先，我争辩说，这种情况不满足（手工易于验证）。如果我们应用我上面描述的方法，我们得到以下“核心”：

$ \存在a \存在c $ $ \ phi（a，c）$ ，< / p>

$ \ phi（a，c）=（\ neg a \ vee c）\ wedge（\ neg c）\ wedge（a \ vee c）$

显然不满足。如果不是这个例子，我们可以看出：

$ \存在a \ forall b \存在c \ forall d $ $ \ psi（a，b，c ，d）$

$ \ psi（a，b，c，d）=（\ neg a \ vee b \ vee \ neg c）\ wedge（\ neg b \ vee c \ Vee d）\ wedge（a \ vee c \ vee \ neg d）$

清晰可满足（将c为true，a至false设置为false），并且具有

的“核心”

$ \存在a \存在c $ $ \ phi（a，c）$ ，< / p>

$ \ phi（a，c）=（\ neg a \ vee \ neg c）\ wedge（c）\ wedge（a \ vee c）$

也与相同的变量设置满意。

如果此方法始终有效，那么似乎暗示从TQBF减少到在通用量词的数量中坐在时间线性和公式中普遍定量变量的出现次数，显示TQBF是NP-COMPLED（已知是PSPACE-CLEATED，因此NP-HARD，因此如果它处于NP-CHINESS中，则此外，NP= PSPACE。如果是这种情况，我会完全震惊，但我一直无法找到一个反例（或在减少的计算成本中缺少，使其不是多项式时间）。我错过了什么？

Answer 1

你的直觉是对的。它不起作用。这是一个反例。

考虑 $ \ forall a \存在b \ varphi（a，b）$ 其中 $ \ varphi（a， b）=（a \ lor \ neg b）\ land（\ neg a \ lor b）$ 。此语句评估为True。

但是，如果我们删除 $ a $ 按照程序，我们会得到 $ \存在b \ psi（b） $ 其中 $ \ psi（b）=（（\ neg b）\ land（b））$ ;那个陈述评估为false。

一种方法来理解为什么你的方法不起作用是 $ \ forall a \存在b \ varphi（a，b）$ 不等同 $ \存在b \ forall a \ varphi（a，b）$ 。最多，如果所有 $ \ forall $ 在内部，即，对于表单 $ \存在\ cdots \存在\ forall \ cdots \ forall $ ，但不是用于 $ \存在$ 和 $ \ forall $ 。