Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/98887
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.
Editor: 
Rights: fechado
Identifier DOI: 10.1016/0304-3975(81)90032-3
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-5844422458&partnerID=40&md5=6884ea245ef84f590f35f97fb7dbd4dc
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.