SPACE-BOUNDED PROBABILISTIC GAME AUTOMATA

被引:11
作者
CONDON, A [1 ]
机构
[1] UNIV WASHINGTON,SEATTLE,WA 98195
关键词
THEORY; ARTHUR-MERLIN GAMES; INTERACTIVE PROOF SYSTEMS; PROBABILISTIC GAME AUTOMATA;
D O I
10.1145/103516.128681
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
New results on the power of space-bounded probabilistic game automata are presented. Space-bounded analogues of Arthur-Merlin games and interactive proof systems, which are denoted by BC and BP respectively, for Bounded random game automata with Complete and Partial information, are considered. The main results are that BC-SPACE(s(n)) sub-set-or-equal-to BP-SPACE(log s(n)) for s(n) = OMEGA(n), union-c DTIME(2cs(n)) = BC-SPACE(s(n)) for s(n) = OMEGA(log n), where s(n) is space constructible. A consequence of these results is that any language recognizable in deterministic exponential time has an interactive proof that uses only logarithmic space. The power of games with simultaneous time and space bounds is also studied, and it is shown that any language in BC-TIME(t(n)) has an interactive proof that uses time polynominal in t(n) but space only logarithmic in t(n).
引用
收藏
页码:472 / 494
页数:23
相关论文
共 27 条
  • [1] [Anonymous], 1988, P 20 ANN ACM S THEOR, DOI 10.1145/62212.62213
  • [2] Babai L., 1985, 17TH P STOC, P421, DOI [10.1145/22145.22192, DOI 10.1145/22145.22192]
  • [3] Brassard G., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P188, DOI 10.1109/SFCS.1986.33
  • [4] ALTERNATION
    CHANDRA, AK
    KOZEN, DC
    STOCKMEYER, LJ
    [J]. JOURNAL OF THE ACM, 1981, 28 (01) : 114 - 133
  • [5] CHAUM D, 1988, 20 STOC, P11
  • [6] PROBABILISTIC GAME AUTOMATA
    CONDON, A
    LADNER, RE
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 36 (03) : 452 - 489
  • [7] CONDON A, 1989, 30TH P ANN S F COMP, P462
  • [8] CONDON A, 1989, 863 U WISC MAD TECH
  • [9] CONDON A, 1988, JUN C STRUCT COMPL T, P162
  • [10] Condon Anne, 1989, COMPUTATIONAL MODELS