🚀 go-pugleaf

In article <By2tv0.BDn.2@cs.cmu.edu> sgall+@CS.CMU.EDU (Jiri Sgall) writes:
>1. I have an explicit algorithm for factoring which is polynomial if P=NP. 
>(No matter if you prove that nonconstructively.)

This is correct: it depends upon the factorization problem being in NP
and co-NP. On input n, the algorithm applies assorted other algorithms
to the number n, in parallel, occasionally adding new ones to the
"pool", and scans the output for a factorization of n, together with a
proof that the factors are prime. There *always* exists a short such
factorization *and* short proof that it is correct. The only problem
is with finding it.

If P=NP, then one of the algorithms out there is a "smart" one which
solves the problem in time polynomial in the length of n (log n). One
will eventually add it to the pool. Of course, you won't know which
one it is, but it will give you the factorization with proof. This
algorithm is hopelessly slow, however, as the constant in the time
required for it to run depends upon the number of algorithms one would
have to search through, one by one, before encountering the magic
algorithm which factorizes quickly.

>2. I have an explicit algorithm that finds a satisfying assignement of a 
>satisfiable formula (but may run forever on an unsatisfiable one) if P=NP.

This is also true, and if P=NP the algorithm can be made to find the
satisfying assignment in polynomial time. Note that this is not the
same as having an algorithm which solves the satisfiability problem,
since you don't know how long you might have to wait for the program
to find the assignment.

*If* you knew what the polynomial was, which bounded the length of
time required to find the assignment, then you *would* be able to make
it into a genuine algorithm for solving the satifiability problem, by
making it stop with a negative result once the time limit has been
passed.

Not having a limit on the size of the algorithm required, and on the
polynomial bounding the length of time it would require to operate, is
the essential reason why one might (so far as we can tell) have a
non-constructive proof of P=NP.

Keith Ramsay
ramsay@unixg.ubc.ca