Article View: comp.theory
Article #1909Suggstion: (was: Re: P=NP; the proof)
From: Mark
Date: Thu, 07 Jan 1993 23:01
Date: Thu, 07 Jan 1993 23:01
25 lines
1681 bytes
1681 bytes
In article <1ifljqINN137@nunki.anu.edu.au> jmr@cs.anu.edu.au (Mike Robson) writes: >>So currently my proof is dead but if you believe in resurrection >>watch this space. > >>Mike Robson. > >AARRGGHH!! > >Jim Reeds has proved that this problem cannot be fixed. 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.
Technical Details
Message-ID:
<1iicnjINNloe@uwm.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!paladin.american.edu!gatech!rpi!uwm.edu!csd4.csd.uwm.edu!markhReferences:
<1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!paladin.american.edu!gatech!rpi!uwm.edu!csd4.csd.uwm.edu!markh From: markh@csd4.csd.uwm.edu (Mark) Newsgroups: comp.theory Subject: Suggstion: (was: Re: P=NP; the proof) Date: 7 Jan 1993 23:01:07 GMT Organization: Computing Services Division, University of Wisconsin - Milwaukee Lines: 25 Distribution: inet Message-ID: <1iicnjINNloe@uwm.edu> References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au> NNTP-Posting-Host: 129.89.7.4 Keywords: Collapse of hierarchy