home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2800 < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  1.5 KB
  1. Path: sparky!uunet!usc!rpi!think.com!enterpoop.mit.edu!eru.mt.luth.se!lunic!sunic!aun.uninett.no!nuug!nntp.nta.no!hal.nta.no!klaus
  2. From: klaus@hal.nta.no (Klaus Gaarder FNI)
  3. Newsgroups: comp.theory
  4. Subject: Re: Probabilistic Turing Machines
  5. Message-ID: <1993Jan6.141449.6860@nntp.nta.no>
  6. Date: 6 Jan 93 14:14:49 GMT
  7. References: <1993Jan5.191925.27528@infodev.cam.ac.uk>
  8. Sender: news@nntp.nta.no
  9. Organization: Norwegian Telecom Research
  10. Lines: 46
  11. Nntp-Posting-Host: periferix.nta.no
  12.  
  13. Consult the paper
  14.  
  15. "Computational Complexity of Probabilistic Turing Machines" by John GILL,
  16. SIAM J of Computing, vol 6, no 4, 1977.
  17.  
  18. THere are also numerous papers on the subject (or related to it) in the
  19. cryptographic litterature on Zero-Knowledge Interactive Proof systems, documented
  20. in eg Springer LNCS proceedings from CRYPTO and EUROCRYPT confs, and the ACM STOC
  21. and FOCS proceedings of later years. Key authors are
  22.  
  23.     S. Goldwasser
  24.  
  25.     S. Micali
  26.  
  27.     C. Rackoff
  28.  
  29.     O. Goldreich
  30.  
  31.     A. Widgerson
  32.  
  33.     G. Brassard
  34.  
  35.     C. Crepeau
  36.  
  37. often in collaboration.
  38.  
  39. Klaus
  40.  
  41.  
  42. *-------------------------------*
  43. | Klaus Gaarder, cand. scient.    |
  44. | Research Scientist        |
  45. | Norwegian Telecom Research    |
  46. | Po Box 83, N-2007 Kjeller    |
  47. | Norway.            |
  48. | Tel: +476 809871        |
  49. | Fax: +476 810076        |
  50. *-------------------------------*
  51.  
  52. -- 
  53.     __o   
  54.   _`\<,_  
  55.  (*)/ (*) Claudio Caputti
  56. +++++++++++++++++++++++++++++++++++++++^++++++++++++++++++++++++++++++++++++++
  57. Free will - the result of chaotic amplification of quantum events in the brain.
  58. ------------------------------------------------------------------------------
  59.