Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: On Tape-bounded Probabilistic Turing Machine Acceptors
Author: Simon J.
Abstract: 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 {A figure is presented} is greater than 1 2. We show that deterministic and probabilistic tape complexities are polynomially related. © 1981.
Rights: fechado
Identifier DOI: 10.1016/0304-3975(81)90032-3
Date Issue: 1981
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
2-s2.0-5844422458.pdf2.07 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.