On probabilistic tape complexity and fast circuits for matrix inversion problems. (English) Zbl 0583.68024

Jung, Hermann

Automata, languages and programming, 11th Colloq., Antwerp/Belg. 1984, Lect. Notes Comput. Sci. 172, 281-291 (1984).

[For the entire collection see Zbl 0543.00014.]
In the first part we propose a complete problem for log n tape bounded probabilistic Turing machines, which interprets the nature of space bounded probabilistic computations as some kind of classical well-known iteration algorithms for solving systems of linear equations. In the second part, we give fast circuits for the inversion of matrices with small bandwidth. As a corollary we obtain new upper bounds for the tape used in the simulation of probabilistic tape bounded Turing machines by deterministic ones.

MSC:

68Q25	Analysis of algorithms and problem complexity
65F99	Numerical linear algebra
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
65F10	Iterative numerical methods for linear systems

Keywords:

tape bounded probabilistic Turing machines; space bounded probabilistic computations; fast circuits for the inversion of matrices with small bandwidth

Citations:

Zbl 0543.00014