用于检查S型的满足性的随机算法，以至少$ frac {2} {3} $输出正确答案

Question

我试图通过随机算法练习自己。

如果它是不可能的，或者它至少具有$ frac {2^n} {n^{10}} $满足分配，那么我们可以通过n变量的cnf公式s-formula s-formula。

我希望您的帮助显示出一种随机算法，以检查S-Formulas的满意度，该算法以至少$ frac {2} {3} $输出正确的答案。

我不太确定如何证明这一点。首先，我的头是这个东西 - 让我们接受概率$ frac {2} {3} $每个输入的概率。然后，如果使用该语言的输入，则可以接受是否在初始折腾（$ frac {2} {3} $）中接受，或者不接受，然后接受它的概率是$ frac {1} {3} {3} CDOT Proibility -to -Peccept $，大于$ frac {2} {3} $。这是这样做的方法，还是我应该以某种方式使用Chernoff不平等，我不确定如何。

Answer 1

基本思想：选择一个随机分配并进行检查。然后，重复多次。即使其中一项作业满足了您回答“是”的公式（否则，您回答“否”）

我们知道输入公式很“简单”：用简单的话来说，这意味着它不可满足 或者 它具有“许多”令人满意的作业。如果不满意 - 无论您选择哪种作业，它将永远无法满足公式。因此，上述算法总是为此类输入正确答案，从这一点开始，我们考虑 只要 令人满意的输入。

如果输入是满足的，那么随机分配满足的可能性是多少？

令$ varphi $为$ n $变量的cnf，超过$ 2^n/n^{10} $满足分配，然后$$ pr_ {x sim u} [ varphi（x）= t] ge frac {2^n/n^{10}}} {2^n} $$

现在我们重复$ k $ times（您必须仔细选择$ k $。让我们稍后再做）。每次我们选择一个随机的$ x $。令$ e_i $是$ i $ -th实例$ varphi $满足的事件。 $ k $尝试后，我们至少发现一个令人满意的任务的概率是多少？

它是$ pr [ bigcup_ {i = 1}^k e_i] $。我们知道$ pr [e_i] ge 1/n^{10} $，您可以使用标准线性（独立事件的）来解决它。

最后一步 - 根据需要找到$ pr [ cup_k e_i] ge 2/3 $的（最小）$ k $。

奖励问题： 如果您使用Chernoff的不平等分析上述内容，您可以制作$ k $（并使算法更有效）？

Answer 2

您的建议不起作用。当公式不满意时，您的算法仅以$ 1/3 $的概率输出正确的答案。

提示：如果一个公式具有$ 2^n/n^{10} $满足分配，那么随机分配满足的可能性是多少？