PCP Theorem by Gap Amplification
PCP Theorem by Gap Amplification
复制标题
能隙放大 PCP 定理
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
B. Vesenmayer
中科院分区：
文献类型：
--
作者：
B. Vesenmayer
PCP 定理提供了 NP 的新分类。自从[AS98]最初的证明以来，出现了几个新的证明。虽然第一个证明使用了高度复杂的方法，但新方法尝试使用更简单的方法。本文给出了[Din05]的证明。它使用该问题与gap-3SAT 的 NP 硬度的等价性，即显示的是该硬度。一组约束的可满足性差距是所有变量分配中不满足约束的最小部分。 Gap-3SAT 是决定这个差距是否为 0 或者大于正常数的问题。因此，在本文中，3SAT 通过间隙放大被多项式简化为间隙-3SAT，即间隙被放大到一个常数分数。
The PCP Theorem provides a new classification of NP. Since the original proof by [AS98], several new proofs occured. While the first proof used highly sophisticated methods, the new approaches try to use simpler ones. In this paper the proof by [Din05] is presented. It uses the equivalence of this problem to the NP-hardness of gap-3SAT, i.e. it is this hardness that is shown. The satisfiability gap of a set of constraints is the smallest fraction of unsatisfied constraints over all assignments for the variables. Gap-3SAT is the problem of deciding whether this gap is 0 or greater than a positive constant. In this paper therefore 3SAT is polynomially reduced to gap-3SAT via gap amplification, i.e. the gap is blown up to a constant fraction.