Hardness Amplification for Errorless Heuristics
Hardness Amplification for Errorless Heuristics
复制标题
无错启发式的硬度放大
DOI：
10.1109/focs.2007.25
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Safra
中科院分区：
文献类型：
--
作者：
Andrej Bogdanov;S. Safra
无误的启发式启发式是一种算法，在所有输入上都返回正确的答案或特殊符号perp，这意味着“我不知道”，平均案例复杂性中的一个核心问题是N P中的每个分配决策问题是否都没有错误启发式方案：这是一种算法，对于每个三角洲> 0，在实例大小和| / delta并仅在三角洲的一个实例中回答perp。我们从硬度放大的角度研究了这个问题，并表明（NP，U）中的每个问题都具有无误的启发式电路，这些电路在n -2/9+Omicron（1） - 输入的分数上输出正确答案，则（NP） ，u）具有非均匀的无误启发式方案。如果（NP，U）中的每个问题都具有随机的无误启发式算法，以在（log n）-1/10+Omicron（1）输入中输出正确答案，则（NP.W）具有随机的无误启发式方案。在这两种情况下，通过分析NP中单调布尔连接的新灵敏度特性来实现低端扩增。在不均匀的环境中，我们使用Benjamini，Schramm和Wilson引入的“全息连接”（Stoc 2005）。对于统一设置，我们引入了一个新的连接点，该连接可以被视为Talagrand的“随机DNF”的有效版本。
An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol perp, which means "I don't know," A central question in average-case complexity is whether every distributional decision problem in N P has an errorless heuristic scheme: This is an algorithm that, for every delta > 0, runs in time polynomial in the instance size and | / delta and answers perp only on a delta fraction of instances. We study the question from the standpoint of hardness amplification and show that If every problem in (NP,U) has errorless heuristic circuits that output the correct answer on n -2/9+omicron(1)-fraction of inputs, then (NP,U) has non-uniform errorless heuristic schemes. If every problem in (NP,U) has randomized errorless heuristic algorithms that output the correct answer on (log n)-1/10+omicron(1)-fraction of inputs, then (NP.W) has randomized errorless heuristic schemes. In both cases, the low-end amplification is achieved by analyzing a new sensitivity property of monotone boolean Junctions in NP. In the non-uniform setting we use a " holographic Junction" introduced by Benjamini, Schramm, and Wilson (STOC 2005). For the uniform setting we introduce a new Junction that can be viewed as an efficient version of Talagrand's "random DNF".