Probabilistic checking of proofs: A new characterization of NP

被引：598

作者：

Arora, S

Safra, S

机构：

[1] Princeton Univ, Princeton, NJ 08544 USA

[2] Tel Aviv Univ, Dept Math, IL-69978 Tel Aviv, Israel

[3] Univ Calif Berkeley, CS Div, Berkeley, CA 94720 USA

[4] Stanford Univ, Stanford, CA 94305 USA

[5] IBM Almaden, San Jose, CA USA

来源：

JOURNAL OF THE ACM | 1998年 / 45卷 / 01期

关键词：

approximation algorithms; complexity hierarchies; computations on polynomials and finite fields; error-correcting codes; hardness of approximations; interactive computation; NP-completeness; probabilistic computation; proof checking; reducibility and completeness; trade-offs/relations among complexity; measures;

D O I：

10.1145/273865.273901

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：70 / 122

页数：53

共 57 条

[1] Ajtai M., 1987, P 19 ANN ACM S THEOR, P132
[2] SIMPLE CONSTRUCTIONS OF ALMOST K-WISE INDEPENDENT RANDOM-VARIABLES
ALON, N
GOLDREICH, O
HASTAD, J
PERALTA, R
[J]. RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (03) : 289 - 304
[3] Arora S., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P2, DOI 10.1109/SFCS.1992.267824
[4] Arora S., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P724, DOI 10.1109/SFCS.1993.366815
[5] Arora S., 1992, P 33 IEEE S FDN COMP, P13
[6] Arora S., 1996, APPROXIMATION ALGORI
[7] ARORA S, 1997, P 29 ANN ACM S THEOR, P496
[8] Arora S., 1996, APPROXIMATION ALGORI
[9] ARORA S, 1992, UNPUB PCP APPROXIMAT
[10] Babai L., 1991, Computational Complexity, V1, P3, DOI 10.1007/BF01200056

← 1 2 3 4 5 6 →