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

Abstract

Chaitin and Schwartz [4] have proved that Solovay and Strassen [12], Miller [9], and Rabin [10] probabilistic algorithms for testing primality are error‐free in case the input sequence of coin tosses has maximal information content.

In this paper we shall describe conditions under which a probabilistic algorithm gives the correct output. We shall work with algorithms having the ability to make “random” decisions not necessarily binary (Zimand [13]). We shall prove that if a probabilistic algorithm is sufficiently “correct”, then it is error‐free on all sufficiently long inputs which are random in Kolmogorov and Martin-Löfs sense. Our result, as well as Chaitin and Schwartz's one, is only of theoretical interest, since the set of all random strings is immune (Calude and Chitescu [2]).

Keywords:

• Kolmogorov complexity
• Martin‐Löfs test
• probabilistic algorithm

C.R. Categories::

• F.1.1
• F.1.2