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 :-(

Any suggestion?

Best regards,

-- J"urgen

--

J"urgen Koslowski | If I don't see you no more in this world

| I meet you in the next world