ARE THERE INTERACTIVE PROTOCOLS FOR CO-NP LANGUAGES

被引：36

作者：

FORTNOW, L ^{[1
]}

SIPSER, M ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY,BERKELEY,CA 94720

来源：

INFORMATION PROCESSING LETTERS | 1988年 / 28卷 / 05期

关键词：

D O I：

10.1016/0020-0190(88)90199-8

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

It is conjectured that co-NP-complete problems do not have interactive protocols. However, a proof of such a statement would imply several well-known unproven complexity conjectures such as P≠NP. This paper instead exhibits an oracle such that relative to this oracle there exists a language in co-NP that does not have an interactive protocol. From this it is shown that techniques that relativize will not settle the conjecture.

引用

页码：249 / 251

页数：3

共 8 条

[1]

Aiello W., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P368, DOI 10.1109/SFCS.1986.36

[2]

Babai Laszlo, 1985, ACM S THEORY COMPUTI, P421, DOI DOI 10.1145/22145.22192

[3]

Baker T., 1975, SIAM Journal on Computing, V4, P431, DOI 10.1137/0204037

[4] DOES CO-NP HAVE SHORT INTERACTIVE PROOFS [J].

BOPPANA, RB ;

HASTAD, J ;

ZACHOS, S .

INFORMATION PROCESSING LETTERS, 1987, 25 (02) :127-132

[5]

FORTNOW L, 1988, IN PRESS 3RD P STRUC

[6]

Goldreich O., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P174, DOI 10.1109/SFCS.1986.47

[7]

GOLDWASSER S, 1986, ADV COMPUTING RES, V5, P59

[8]

GOLDWASSER S, 1985, 17 ACM S THEOR COMP, P291

← 1 →