FOM: Primality testing -- reply to Fenner
Joe Shipman
shipman at savera.com
Mon Oct 19 14:17:49 EDT 1998
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
More information about the FOM
mailing list