Let be the probability that a given algorithm gives the correct
answer for input . We are also interested in , which is the
average of over all squares , and , the average over
all pseudo-squares, and , the average of over all .
If we are given an algorithm, we can easily determine by
running it with input on a sample of randomly chosen and
counting the number of times the algorithm answers ``this is a square.''
The procedure for determining is more elaborate. Suppose we
have an algorithm for which . Using Lemma 26, generate
a sample of 100 members of , and run the algorithm on each of them.
Suppose we get the answer ``this is a square'' 65 times. There are
squares in the sample, on which there have been .6(50) correct
responses and 20 incorrect. Pseudo-squares have been identified as
squares times, which suggests
. Finally
.
Lemma 24 or 25 can
be used to determine the probability that these estimates come within
a specified amount.