home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2797 < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  2.2 KB
  1. Path: sparky!uunet!usc!cs.utexas.edu!sun-barr!olivea!spool.mu.edu!yale.edu!cs.yale.edu!ginkgo.theory.cs.yale.edu!fischer
  2. From: fischer-michael@cs.yale.edu (Michael Fischer)
  3. Newsgroups: comp.theory
  4. Subject: Re: Probabilistic Turing Machines
  5. Message-ID: <1993Jan6.033354.4587@cs.yale.edu>
  6. Date: 6 Jan 93 03:33:54 GMT
  7. References: <1993Jan5.191925.27528@infodev.cam.ac.uk>
  8. Sender: news@cs.yale.edu (Usenet News)
  9. Reply-To: fischer-michael@cs.yale.edu (Michael Fischer)
  10. Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
  11. Lines: 33
  12. Nntp-Posting-Host: ginkgo.theory.cs.yale.edu
  13. X-Newsreader: TIN [version 1.1az (for az) PL8]
  14.  
  15. Nick Maclaren (nmm1@cus.cam.ac.uk) wrote:
  16.  
  17. : Consider standard deterministic Turing machines with a fixed, finite program
  18. : and an arbitrary input tape (i.e. the input is deemed separate from the
  19. : program.  Consider probabilistic versions with the program extended to
  20. : allow the generation of a true random bit.
  21.  
  22. : Clearly the second model is strictly more powerful than the first, but I
  23. : am interested (for now) only in deterministic problems - that is ones
  24. : where the output and termination (if any) depend solely on the input tape.
  25.  
  26. : 1) Is it known whether there are any deterministic problems that can be
  27. : solved by probabilistic Turing machines but not by deterministic ones?
  28.  
  29. : 2) Is it known that there are no such algorithms?
  30.  
  31. : 3) Assuming (2), are there any deterministic problems that have a lower
  32. : complexity for probabilistic Turing machines than deterministic ones?
  33.  
  34. : 4) Is is known that there are no such problems?
  35.  
  36. If I understand your questions, the answers to (2) and (4) are both
  37. trivially "no".  To say that a probabilistic machine's output and
  38. termination depend solely on the input tape means that its behavior is
  39. the same on all sequences of bits that might result from the random
  40. bit generator.  In particular, its output and termination will be the
  41. same on the sequence of all 0's.  By fixing each random bit to 0, it
  42. is easy to convert the probabilistic Turing machine into an equivalent
  43. deterministic one.
  44.  
  45. ==================================================
  46. | Michael Fischer <fischer-michael@cs.yale.edu>  |
  47. ==================================================
  48.