I have to come back to the BPP-question I asked before. This class
consists of the languages L with the following property:
There exists a precise polynomially bounded TM with degree of non-
determinacy <= 2, such that the probability of false positives *AND*
the probability of false negatives are less than 1/4.
(Here "precise" means that all computations for an input x use the
same number of steps, given by a polynominal in the length of x.)
Question: is BPP closed under union?
Simply composing two such TM's in series yields a TM that can be made
precise in the sense above quite easily, but only has probabilities
for false posititves and false negatives of less than 5/16. The
suggestion had been to iterate such TM's in order to lower this bound.
But it seems as if we can only lower the probability of false positives
in this fashion, or the probability of false negatives, but not both
simultaneously. (For inputs in L_0\cup L_1 we want to accept if at
least one run accepts, and for inputs not in this union we want to
reject if at least one run rejects. But for this we need to know in
advance whether the input is in the union or not :-(
J"urgen Koslowski | If I don't see you no more in this world
| I meet you in the next world