FOM: nonconstructive existence proofs of algorithms
JoeShipman at aol.com
Thu Aug 10 01:21:21 EDT 2000
In a message dated 8/9/00 4:18:59 PM Eastern Daylight Time,
simpson at math.psu.edu writes:
<< Thus we have a nonconstructive proof that for each n there exists a
PTIME algorithm for deciding whether a given finite graph is of genus
greater than n. We do not have the algorithms themselves. >>
Excellent example! But in the case of sets we know *constructively* are in
NP intersect co-NP, we can construct a general-purpose algorithm for deciding
membership in the set (run all possible polynomial time witness-finding and
anti-witness-finding algorithms in parallel) which runs in polynomial time if
the set is in P.
Actually, there is a slight caveat here -- if the set is in P then there is
not necessarily a polynomial time witness-finding/anti-witness-finding
algorithm for the PARTICULAR pair of nondeterministic algorithms which we
*constructively* knew placed the set in NP intersect co-NP, but in many
problems of interest this is not an issue.
For example, consider the following factoring algorithm: Input is N.
Assume an enumeration of algorithms with input N. Run the first algorithm
for 1 step, the first 2 algorithms for 2 steps, the first 3 algorithms for 3
steps, and so on; whenever an algorithm halts test the output to see if it is
either a factor of N or a Pratt-style certificate of N's primality.
Although this seems amazingly slow, if there is a PTIME algorithm for
factoring integers then this algorithm will also run in PTIME (with a
constant bigger than the number of atoms in the Universe, alas).
(For this to work, there has to be a PTIME algorithm which can not only
produce a factor of N if N is composite but also produce a certificate if N
is prime; however, any algorithm that finds a nontrivial factor or correctly
announces "Prime" can be converted into a not-much-slower algorithm that does
the certificates too by recursively factoring n-1 and certifying its factors.)
Can anyone tell me who first discovered this construction? Adleman does
something like it in an old paper on factoring, but it may be older than that.
-- Joe Shipman
More information about the FOM