A relation between correctness and randomness in the computation of probabilistic algorithms

References

• Calude , C. 1982 . “ Computational Complexity, Qualitative Aspects ” . Romanian : Bucuresti . Editura ştiinţific[acaron] şi enciclopedici[acaron]
   Google Scholar
• Calude , C. and Chiţescu , I. 1982 . Strong noncomputability of random strings . Internat. J. Comput. Math , 11 : 43 – 45 .
   Web of Science ®Google Scholar
• Calude , C. and Chiţescu , I. 1982 . Classical approach . Found. Control Engrg , 7 : 73 – 85 . Random strings according to A. N. Kolmogorov and P. Martin-Löf
   Google Scholar
• Chaitin , G. J. and Schwartz , J. T. 1978 . A note on Monte Carlo primality tests and algorithmic information theory . Comm. Pure Appl. Math , 31 : 521 – 527 .
   Web of Science ®Google Scholar
• Gill , J. T. 1977 . Computational complexity of probabilistic Turing machines . SIAM J. Comput , 6 : 675 – 695 .
   Web of Science ®Google Scholar
• Kolmogorov , A. N. 1965 . Three approaches to the quantitative definition of information . Problemy Peredachi Informatsii , 1 : 1-7 Russian
   Google Scholar
• Machtey , M. and Young , P. 1978 . An Introduction to the General Theory of Algorithms , North-Holland : Amsterdam .
   Google Scholar
• Martin ‐ Löf , P. 1966 . The definition of random sequences . Inform. and Control , 10 : 602 – 619 .
   Google Scholar
• Miller , G. L. 1976 . Riemann's hypothesis and tests of primality . J. Comput. System Sci , 13 : 300 – 317 .
   Web of Science ®Google Scholar
• Rabin , M. O. 1976 . “ Probabilistic algorithms ” . In In Algorithms and Complexity. New Directions and Recent Results , Edited by: Traub , J. F. 21 – 39 . New York : Academic Press .
   Google Scholar
• Rogers , H. 1967 . Theory of Recursive Functions and Effective Computability , New York : McGraw‐Hill .
   Google Scholar
• Solovay , R. and Strassen , V. 1977 . A fast Monte‐Carlo test for primality . SIAM J. Comput , 6 : 84 – 85 . Erratum 7 (1978), 118
   Google Scholar
• Zimand , M. 1982 . Complexity of probabilistic algorithms. Preliminary report . Abstracts of Papers Presented to AMS , 82 ( T-68-525 ) : 547
   Google Scholar
• Zimand , M. 1983 . Complexity of probabilistic algorithms. Preliminary report . Control Engrg , 8 ( T-68-525 ) : 33 – 49 .
   Google Scholar