帮助位对随机和平均情况复杂性中的价值

1−--帮助位在随机和平均情况复杂性中的价值Salman Beigi1，Omid Etesami1，and Amin Gohari1， 21伊朗德黑兰基础科学研究所数学学院2伊朗德黑兰谢里夫理工大学电气工程系二O一四年七月六日摘要“HLP比特”是在计算问题的一个或多个实例中针对可降低求解该一个或多个实例的计算复杂性的计算问题的一个或多个实例而定义的一种有限的规则。在本文中，我们研究的帮助位的随机和平均情况下的复杂性设置的价值Amir，Beigel和Gasarch（1990）表明，对于常数k，如果决策问题的k个实例可以使用少于k位的帮助有效地解决，那么问题是在P/ poly中。我们将这一结果扩展到随机计算的设置：我们表明，决策问题是在P/聚，如果使用100个帮助位，k个问题的实例可以有效地解决的概率大于2<$−k。如果使用少于k（1h（α））个帮助比特（其中h（α）是二进制熵函数），则同样的结果成立，我们可以有效地以非零概率正确地求解实例的（1α我们还将这两个结果推广到非常数但对数k。然而，在这种情况下，不是示出问题在P/poly中，而是示出它是 有 限 的 “ k 个 最 小 的 最 小 的 最接下来我们考虑平均情况复杂度的设置：假设我们可以使用一些熵小于k的帮助位来解决决策问题的k个实例，当k个实例独立于特定分布时。然后，我们可以有效地解决从该分布中提取的实例，其概率优于1/ 2。最后，我们表明，在k是超对数的情况下，假设k-成员的决策问题的可比性，一个不能证明，该问题是在P/poly由一个“b l a c k - b o x p r o o f”。1介绍在并行计算中，“驱动”可以是将一个外部输入（除了输入实例之外）用于尝试解决计算问题的算法。Advice仅依赖于输入实例的大小，并捕获非统一的计算模型。在本文中，我们感兴趣的是一个额外的输入，不像建议取决于要解决的问题的特定实例。这种额外的输入（givevenas是比特的提取）被认为是“hel p比特”。这些建议是一种算法的输入，类似于建议，由可信的计算无界方生成，但与建议不同的是，它取决于问题的实例，而不仅仅是它的大小。我们将在使用该“hel p er”的hel p b it时使用该“hel p er”。“arXiv：1408.0499v1 [cs.CC] 2014年8月2∩帮助位也可以从oracle模型的角度来理解给定一个问题的实例，我们可以询问一个预言机对应于该实例的帮助位，然后尝试解决它。实际上，对于k位的帮助，来自预言机的k个yes/no查询在这里，神谕扮演着帮助者的角色。然而，预言机可以自适应地使用：对预言机的查询可能取决于对先前查询的回答，但是帮助位不能自适应地请求，并且仅在算法开始时给出。这种差异应更仔细地考虑在概率以及非确定性模型的计算。这里的另一个问题是帮助位的长度。对于k个帮助位，我们应该将oracle的使用限制为k个yes/no查询，而不是（比如说）多项式多的查询。任何决策问题都可以通过一个帮助位有效地解决，因为我们可以通过这一点帮助来要求帮助者给我们决策问题的是/否答案。因此，为了获得有意义的问题，我们考虑每个实例少于例如，有人可能会问：我们可以在多项式时间内用k−1个帮助位同时解决NP难决策问题的k个实例吗？也就是说，我们能否巧妙地设计这k-1个帮助位，使所有k个实例都能有效地求解？假设有一个有效的算法，给定k个实例x1，. . .，x k和0时，最小多项式（x_n（n）/n）s（n）的circ算法不能计算（L（x_1），. . . ，L（xk））。 x1，. . . ，x k∈ {0，1}，其中每个x i根据D选择，概率优于p（n）+n。熵，互信息：在下面，我们将回顾一些信息理论量的定义和性质，这些量将在第4节中使用。对于离散随机变量X，由H（X）表示的X的熵定义为：显然，H（X）=Σ1p（x）lg 2p（x）.X1H（X）≥lg2max.（一）p（x）当X是具有参数p的伯努利随机变量时，熵函数被写为1 1h（p）= p lg p+（1 − p）lg 1 − p。X6|固定X的字母集的大小为m，H（X）的最大值在均匀分布时达到，并且等于lg（m）。对于两个离散随机变量X，Y，条件熵H（X|（Y）定义通过H（X|Y）= Σp（y）H（XY=y），y其中H（X|Y = y）是具有分布p（x）的随机变量的熵|y）。条件熵H（X|如果X是Y的函数，则x（Y）为零。也很容易看出，H（X|Y）= H（X，Y）− H（Y）。两个随机变量X和Y之间的互信息定义为：I（X; Y）= H（X）− H（Y |X）= H（Y）− H（Y |X）= H（X）+H（Y）− H（X，Y）。我们总是有I（X;Y）≥ 0。给定三个随机变量，条件互信息定义为：I（X; Y |Z）= H（X|Z）− H（X|Y，Z）= H（Y |Z）− H（Y |X，Z）。我们又有I（X; Y|Z）≥ 0。注意，I（X; Y|Z）= 0，如果例如X是Z的函数。下面的公式很容易被验证，被称为链式法则：I（X; Y Z）= I（X; Y）+I（X; Z|Y）。3随机复杂性在 下 面 的 定 理 中 ， 我 们 证 明 了 随 机 帮 助 位 不 能 增 加 正 确 找 到 （ L（x1），. . .，L（x k））的系数大于2 l，除非L是非均匀k-隶属度可比的。定理5设 0，0 <α，λ <1/2为常数，L为语言。也令k=O（lg n）.我们给出k个任意实例x1，. . .，x k的L.(i) 假设使用

下载后可阅读完整内容，剩余1页未读，立即下载