ARTHUR-MERLIN GAMES - A RANDOMIZED PROOF SYSTEM, AND A HIERARCHY OF COMPLEXITY CLASSES

被引:286
作者
BABAI, L
MORAN, S
机构
[1] UNIV CHICAGO, CHICAGO, IL 60637 USA
[2] TECHNION ISRAEL INST TECHNOL, HAIFA, ISRAEL
关键词
D O I
10.1016/0022-0000(88)90028-1
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
45
引用
收藏
页码:254 / 276
页数:23
相关论文
共 45 条
[1]  
Adleman L., 1978, 19th Annual Symposium on Foundations of Computer Science, P75, DOI 10.1109/SFCS.1978.37
[2]  
AIELLO W, 1986, IN PRESS COMBINATORI, P368
[3]  
Babai L., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P229, DOI 10.1109/SFCS.1984.715919
[4]  
Babai L., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P337, DOI 10.1109/SFCS.1986.15
[5]  
Babai L., 1983, 15 ANN ACM S THEOR C, P171
[6]  
BABAI L, IN PRESS RANDOMNESS
[7]  
BABAI L, 1982, ANN DISCRETE MATH, V12, P27
[8]  
BABAI L, UNPUB COMPLEXITY MAT
[9]  
Babai Laszlo, 1985, ACM S THEORY COMPUTI, P421, DOI DOI 10.1145/22145.22192
[10]   RELATIVE TO A RANDOM ORACLE-A, PA NOT-EQUAL NPA NOT-EQUAL CO-NPA WITH PROBABILITY-1 [J].
BENNETT, CH ;
GILL, J .
SIAM JOURNAL ON COMPUTING, 1981, 10 (01) :96-113