Computational Complexity of Probabilistic Turing Machines
1977; Society for Industrial and Applied Mathematics; Volume: 6; Issue: 4 Linguagem: Inglês
10.1137/0206049
ISSN1095-7111
Autores Tópico(s)Cellular Automata and Applications
ResumoA probabilistic Turing machine is a Turing machine with the ability to make decisions based on the outcomes of unbiased coin tosses. The partial function computed by a probabilistic machine is defined by assigning to each input the output which occurs with probability greater than $\frac{1}{2}$. With this definition, only partial recursive functions are probabilistically computable. The run time and tape of probabilistic machines are defined. A palindrome-like language is described that can be recognized faster by one-tape probabilistic Turing machines than by one-tape deterministic Turing machines. It is shown that every nondeterministic machine can be simulated in the same space by a probabilistic machine with small error probability. Several classes of languages recognized probabilistically in polynomial time are defined and compared with $NP$.
Referência(s)