## BPP again

### BPP again

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

### BPP again

> 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.

It's some time since I've done any of this (so maybe I should keep
quiet!) but can't you just repeat the computation a few times and
then take a majority vote on the outcome? If x is in L1, then T1
(which accepts L1) will almost certainly accept more than 50% of
the time (and conversely, for x not in L1, T1 will reject the majority).
Likewise for L2 and T2.

James
--
James Annan jdan(at)pol(dot)ac(dot)you-kay
Proudman Oceanographic Lab
Bidston, Merseyside, L43 7RA

### BPP again

|>
|> > 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.
|>
|> It's some time since I've done any of this (so maybe I should keep
|> quiet!) but can't you just repeat the computation a few times and
|> then take a majority vote on the outcome? If x is in L1, then T1
|> (which accepts L1) will almost certainly accept more than 50% of
|> the time (and conversely, for x not in L1, T1 will reject the majority).
|> Likewise for L2 and T2.

You can.  You can also work out the optimal strategy.  See sequential
sampling in any decent (and moderately advanced) book on statistics.

Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.

Tel.:  +44 1223 334761    Fax:  +44 1223 334679

### BPP again

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

I certainly am statistically challenged, but here the problem simply
was that one ought to run the machine an *odd* number of times for
for majority decisions to make sense.  Then the behaviour is indeed
symmetric for false positives and false negatives.  (For even numbers
of runs one may have to throw a fair coin to decide in case of ties.)

-- J"urgen

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

{<M,x> | M is a two sided error NDTM accepting x in at most |x|^2 steps}
is a hard problem for BPP.
It is not complete "because" of the fact that deciding wether a NDTM is
a BPP one is undecidable.
It it quite obviously a hard problem for BPP...Not so obviously realy.
What's puzzling me is the need to have the TM accepting in time |x|^2.
Why is it that linear time won't do, just as in the NP-case:

{<M,x> | M is a  NDTM accepting x in at most |x| steps} is a NP-hard
problem. (Even complete in fact.)

I must be missing something...

Thanks for any help.
Best regards, O.Powell

13. Taj (again)