Probabilistic checking of proofs: a new characterization of NP
发表信息
作者
- Sanjeev Arora
- Shmuel Safra
笔记
Abstract We give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in polynomial time using logarithmic number of random bits and by reading sublogarithmic number of bits from the proof. We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.
我们给出了 NP 的一个新特征：类 NP 精确地包含那些语言 L，对于这些语言，成员证明（证明输入 x 属于 L）可以在多项式时间内通过使用对数数量的随机位和读取证明中的次对数位来进行概率验证。我们讨论了这一特征的含义；具体而言，我们展示了即使在非常弱的意义上，近似最大团（Clique）和独立集（Independent Set）也是 NP-hard 的。