Interactive proofs and the hardness of approximating cliques

被引：280

作者：

Feige, U

Goldwasser, S

Lovasz, L

Safra, S

Szegedy, M

机构：

[1] MIT, DEPT ELECT ENGN & COMP SCI, CAMBRIDGE, MA 02139 USA

[2] YALE UNIV, DEPT COMP SCI, NEW HAVEN, CT 06517 USA

[3] AT&T BELL LABS, MURRAY HILL, NJ 07974 USA

来源：

JOURNAL OF THE ACM | 1996年 / 43卷 / 02期

关键词：

hardness of approximation; independent set in a graph; multilinearity testing; np-completeness; probabilistically checkable proofs;

D O I：

10.1145/226643.226652

中图分类号：

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

学科分类号：

0812 ;

摘要：

The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP languages is constructed, where the verifier uses very few random bits and communication bits. Last, the connection between cliques and efficient multi-prover interactive proofs, is shown to yield hardness results on the complexity of approximating the size of the largest clique in a graph. Of independent interest is our proof of correctness for the multilinearity test of functions.

引用

页码：268 / 292

页数：25

共 34 条

[1] THE MONOTONE CIRCUIT COMPLEXITY OF BOOLEAN FUNCTIONS
ALON, N
BOPPANA, RB
[J]. COMBINATORICA, 1987, 7 (01) : 1 - 22
[2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[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, 1992, AN S FDN CO, P14
[5] Babai L., 1991, Computational Complexity, V1, P3, DOI 10.1007/BF01200056
[6] Babai Laszlo, 1991, P 23 ANN ACM S THEOR, P21, DOI [10.1145/103418.103428, DOI 10.1145/103418.103428]
[7] BARYEHUDA R, 1983, 260 TECHN
[8] Ben-Or M., 1988, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, P113, DOI 10.1145/62212.62223
[9] BERGER B, 1990, ALGORITHMICA, V5, P459, DOI 10.1007/BF01840398
[10] ON THE COMPLEXITY OF APPROXIMATING THE INDEPENDENT SET PROBLEM
BERMAN, P
SCHNITGER, G
[J]. INFORMATION AND COMPUTATION, 1992, 96 (01) : 77 - 94

← 1 2 3 4 →