On probabilistic time and space. (English) Zbl 0599.68043

Jung, Hermann

Automata, languages and programming, 12th Colloq., Nafplion/Greece 1985, Lect. Notes Comput. Sci. 194, 310-317 (1985).

[For the entire collection see Zbl 0563.00018.]
We prove that inequalities of arithmetic expressions over the ring of \(n\times n\) matrices can be decided by probabilistic Turing machines working simultaneously within O(log n) space and polynomial time. As a corollary we obtain: PrSPACE(log n)\(=\Pr TISP(n^{O(1)},\log n)\), which solves a problem that has been open for a long time.

MSC:

68Q25

Analysis of algorithms and problem complexity

Keywords:

inequalities of arithmetic expressions; probabilistic Turing machines

Citations:

Zbl 0563.00018