On Tape-Bounded Probabilistic Turing Machine Acceptors
On Tape-Bounded Probabilistic Turing Machine Acceptors
复制标题
关于带限概率图灵机接受器
DOI：
10.1016/0304-3975(81)90032-3
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
Janos Simon
中科院分区：
文献类型：
--
作者：
Janos Simon
概率图灵机接受者是一种图灵机接受者，它投掷无偏硬币来决定下一步该怎么走，如果达到最终接受的概率大于12，就接受它的输入。我们证明了确定性和概率磁带复杂性是多项式相关的。
A probabilistic Turing machine acceptor is a Turing machine acceptor that flips unbiased coins to decide what its next move will be and accepts its input if the probability of reaching a final accepting is greater than 1 2. We show that deterministic and probabilistic tape complexities are polynomially related.