Clique is hard to approximate within n1-ε

被引：583

作者：

Håstad, J ^{[1
]}

机构：

[1] Royal Inst Technol, Dept Math, SE-10044 Stockholm, Sweden

来源：

ACTA MATHEMATICA | 1999年 / 182卷 / 01期

关键词：

D O I：

10.1007/BF02392825

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

[No abstract available]

引用

页码：105 / 142

页数：38

共 34 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] Probabilistic checking of proofs: A new characterization of NP [J].

Arora, S ;

Safra, S .

JOURNAL OF THE ACM, 1998, 45 (01) :70-122

[3]

ARORA S, 1992, IN PRESS J ACM

[4]

Babai L., 1991, Computational Complexity, V1, P3, DOI 10.1007/BF01200056

[5]

BABAI L, 1985, 17 ANN ACM S THEOR C, P420

[6]

BABAI L, 1991, 23 STOC, P21

[7] Free bits, PCPs, and nonapproximability - Towards tight results [J].

Bellare, M ;

Goldreich, O ;

Sudan, M .

SIAM JOURNAL ON COMPUTING, 1998, 27 (03) :804-915

[8] Linearity testing in characteristic two [J].

Bellare, M ;

Coppersmith, D ;

Hastad, J ;

Kiwi, M ;

Sudan, M .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1996, 42 (06) :1781-1795

[9]

BELLARE M, 1993, 25TH P ACM S THEOR C, P294

[10]

BELLARE M, 1994, 26TH P ANN ACM S THE, P184

← 1 2 3 4 →