On tape Bounded probabilistic turing machine transducers

Publisher Website

1 October 1978

proceedings article
Published by Institute of Electrical and Electronics Engineers (IEEE)

https://doi.org/10.1109/sfcs.1978.27

Abstract

The tape requirements of probabilistic and deterministic Turing machine transducers are polynomially related.

Keywords

This publication has 5 references indexed in Scilit:

Computational Complexity of Probabilistic Turing Machines
SIAM Journal on Computing, 1977
A characterization of the power of vector machines
Journal of Computer and System Sciences, 1976
On the Structure of Feasible Computations
Published by Elsevier ,1976
On the power of multiplication in random access machines
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1974
Relationships between nondeterministic and deterministic tape complexities
Journal of Computer and System Sciences, 1970