home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2842 < prev    next >
Encoding:
Text File  |  1993-01-08  |  1.1 KB  |  29 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!pipex!ibmpcug!exnet!dcs.ed.ac.uk!pdc
  3. From: pdc@dcs.ed.ac.uk (Paul Crowley)
  4. Subject: Re: Probabilistic Turing Machines
  5. Message-ID: <C0KAGr.GDu@dcs.ed.ac.uk>
  6. Sender: cnews@dcs.ed.ac.uk (UseNet News Admin)
  7. Reply-To: pdc@dcs.ed.ac.uk (Paul Crowley)
  8. Organization: Edinburgh University
  9. References: <1993Jan5.191925.27528@infodev.cam.ac.uk> <1993Jan6.033354.4587@cs.yale.edu>
  10. Date: Sat, 9 Jan 1993 00:53:14 GMT
  11. Lines: 16
  12.  
  13. Quoting fischer-michael@cs.yale.edu (Michael Fischer) in article <1993Jan6.033354.4587@cs.yale.edu>:
  14. >
  15. >: 3) Assuming (2), are there any deterministic problems that have a lower
  16. >: complexity for probabilistic Turing machines than deterministic ones?
  17. >
  18. >: 4) Is is known that there are no such problems?
  19.  
  20. >If I understand your questions, the answers to (2) and (4) are both
  21. >trivially "no".
  22.  
  23. What happens if we ask only that the probability that the program fails
  24. to complete within the lower time bound tends to zero as the size of the
  25. problem tends to infinity?
  26.   __                                _____
  27. \/ o\ Paul Crowley pdc@dcs.ed.ac.uk \\ //
  28. /\__/ "I'm the boy without a soul."  \X/ 
  29.