FOM: nonconstructive existence proofs of algorithms

[JoeShipman@aol.com]

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