Interactive proofs and the hardness of approximating cliques

被引：285

作者：

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 [J].

ALON, N ;

BOPPANA, RB .

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 [J].

BERMAN, P ;

SCHNITGER, G .

INFORMATION AND COMPUTATION, 1992, 96 (01) :77-94

← 1 2 3 4 →