🚀 go-pugleaf

markh@csd4.csd.uwm.edu (Mark) writes:

[historical allusions deleted]

>When you come up with a P=NP proof, first make sure you can translate it to
>several of the other known NP-complete problems.  Each conversion should lead
>to some significant result and insight if the original proof is correct.
>Also, you'd get far more attention by simultaneously publicising polynomial
>algorithms for 10 to 20 NP-complete problems, and a single tenuous and
>highly abstract proof.  The conversions are in the literature, so it's
>a trivial bookkeeping process to develop 20 algorithms from one.

>Second, test the thing out before publicising it, by running the algorithms on
>actual cases and then using these test cases to exemplify the algorithms when
>you do publicise them.

>If you're refereeing journals or otherwise trying to determine the validity
>of P=NP proofs, reject all alleged proofs that don't meet the two criteria
>above.

Thanks for the suggestion.

I've just come up with a fantastic n^12 algorithm for the subset sum
problem which translates into a n^24 algorithm for SAT which gives me
a n^48 algorithm for graph isomorphism. As soon as I have tested this
on a few non trivial pairs of nonisomorphic graphs I'll submit
it to CACM (or whatever journal seesm appropriate in 100993).


More seriously: we all know about the conversions so why bother
elaborating them. If it turns out that P=NP (I doubt it today),
then it is the fact that matters.


Mike Robson.