Testing of the long code and hardness for clique
Testing of the long code and hardness for clique
复制标题
派系长码及硬度测试
DOI：
10.1145/237814.237820
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
J. Håstad
中科院分区：
文献类型：
--
作者：
J. Håstad
我们证明了除非NP = COR，否则对于任何c >，在系数ni /2 ' c范围内很难用多项式时间来近似最大团。这是通过构造NP w的证明系统来实现的，该系统对任意i >使用1+6个平摊自由位。我们以Bellare、Goldreich和Sudan的证明系统为基础，同时用一种宽松的码字测试取代他们对长代码的严格码字测试，这足以满足目前的目的。这个测试的结论是，如果测试不拒绝。，则除了极小概率y外，测试所看到的与少数可能的密码字之一一致。
We prove that unless NP = COR, Max Clique is hard to approximate wit hin polynomial time within a factor ni /2 ‘c for any c >0. This is done by constructing a proof system for NP w hich uses 1+6 amortized free bits for any ii >0. We build on the proof system of Bellare, Goldreich and Sudan, while seplacing their strict code-word test for the long code by a relaxed code-word test which is sufficient for the present purposes. The conclusion of this test is that if the test does not reject., then except wit h very small probability y, what the test saw is consistent with one of few possible code-words.