Space bounded probabilistic game automata
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 162-174
- https://doi.org/10.1109/sct.1988.5276
Abstract
Results on the power of space-bounded probabilistic game automata are presented. Space-bounded analogs of Arthur-Merlin games and interactive proof systems are considered for bounded random game automata with complete and partial information. A consequence of the 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 NTIME(t(n)) has an interactive proof that uses time polynomial in t(n) but space only logarithmic in t(n).Keywords
This publication has 0 references indexed in Scilit: