FOM: Primality testing -- reply to Fenner

[Joe Shipman]

Thanks for the reference.  Adleman's sure done a lot of good stuff,
hasn't he?

So what's the best example of a problem in BPP but *not* known to be in
"polynomial expected time"?  The difference between these two classes is
that a BPP-algorithm  gives you almost-certain information about
membership while a "PET-algorithm" (what's the standard abbreviation
here?) almost certainly gives you a short (classically valid) *proof* of
membership or non-membership.

What is the opinion of most complexity theorists on whether PET=P and
whether BPP=P?  The first of these seems as close as a complexity class
could get to P without actually being P.  If  good polynomial-time
pseudo-random number generators exist then BPP=P but not effectively;
however PET would effectively equal P.

-- Joe Shipman