论文标题
非 - 亚伯群体的最佳$ k $ -lin的最佳不Xibibibibibibibibility
Optimal Inapproximability of Satisfiable $k$-LIN over Non-Abelian Groups
论文作者
论文摘要
Håstad的开创性结果[J。 ACM，48（4）：798--859，2001]表明，找到满足$ \ frac {1} {1} {| g |}+\ varepsilon $约束的$ k $ -lin实例的约束的任务的任务是np-hard，即使在任何满足$（1- $ abelian flof）的约束方面，$ n vers contrive $ nvers contription $ n varron contription $（1-）常数$ \ varepsilon> 0 $。 Engebretsen等。 [理论计算机科学，312（1）：17--45，2004]后来表明，与任何有限的非亚伯利亚群体相比，$ k $ -lin实例相同的硬度结果。 与阿贝尔案不同，如果在非阿布尔情况下，我们可以有效地找到解决方案的情况，那么决定给定的线性方程式是否满足，NP完整是完整的，如Goldmann和Russell [信息与计算，178（1）：253--262。 2002]。 出乎意料的是，对于某些非亚洲群体$ g $，鉴于$ g $上令人满意的$ k $ -lin实例，实际上，一个人可以做得更好，而不是仅仅使用简单但聪明的算法输出随机分配。该算法获得的近似因子随基础组而变化。在本文中，我们证明了该算法是{\ em optimal}，证明了可满足的$ k $ -lin实例的紧密硬度，而不是{\ em any} non-Abelian $ g $，假设$ p \ p \ neq np $。 作为推论，我们还获得了$ 3 $ Query的概率可检查的证明，并且在大型字母上具有完美的完整性，并提高了声音。
A seminal result of Håstad [J. ACM, 48(4):798--859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant $\varepsilon>0$. Engebretsen et al. [Theoretical Computer Science, 312(1):17--45, 2004] later showed that the same hardness result holds for $k$-LIN instances over any finite non-abelian group. Unlike the abelian case, where we can efficiently find a solution if the instance is satisfiable, in the non-abelian case, it is NP-complete to decide if a given system of linear equations is satisfiable or not, as shown by Goldmann and Russell [Information and Computation, 178(1):253--262. 2002]. Surprisingly, for certain non-abelian groups $G$, given a satisfiable $k$-LIN instance over $G$, one can in fact do better than just outputting a random assignment using a simple but clever algorithm. The approximation factor achieved by this algorithm varies with the underlying group. In this paper, we show that this algorithm is {\em optimal} by proving a tight hardness of approximation of satisfiable $k$-LIN instance over {\em any} non-abelian $G$, assuming $P \neq NP$. As a corollary, we also get $3$-query probabilistically checkable proofs with perfect completeness over large alphabets with improved soundness.
