SPACE-BOUNDED PROBABILISTIC GAME AUTOMATA

被引：11

作者：

CONDON, A ^{[1
]}

机构：

[1] UNIV WASHINGTON,SEATTLE,WA 98195

来源：

JOURNAL OF THE ACM | 1991年 / 38卷 / 02期

关键词：

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 条

[11] DWORK C, 1988, RJ626261659 IBM ALM
[12] FEIGE U, 1987, 19TH P ANN ACM S THE, P210
[13] FORTNOW L, 1988, UNPUB INTERACTIVE PR
[14] FORTNOW L, 1989, MIT LCS TR447 TECH R
[15] Garey M. R., 1979, COMPUTERS INTRACTIBI
[16] Golawasser S., 1982, P 14 ANN ACM S THEOR, P365
[17] Goldreich O., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P174, DOI 10.1109/SFCS.1986.47
[18] GOLDWASSER S, 1985, 17 ACM S THEOR COMP, P291
[19] KILLIAN J, 1988, 29TH P IEEE S F COMP, P25
[20] GAMES AGAINST NATURE
PAPADIMITRIOU, CH
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 31 (02) : 288 - 301

← 1 2 3 →