What to do?

[snow5379]

I've found an algorithm that solves NP complete problems in polynomial time. What do I do now? And yes I know you don't believe me but that's beyond the point... how should I publish it? I'm not willing to share it here because I have nothing to really prove... I'm just looking for information on how to publish my findings.

[poxic]

Here's a link on MathOverflow with tips on this process.

Edit: and a link to computing science journals, which probably have similar submissions processes.

[snow5379]

Thanks.

[Yakk]

Are you willing to entertain a reasonable dollar value binding bet with even odds on the subject (of whether or not your algorithm proves P=NP)?

(Note that being able to solve some, or even most, instances of an NP-complete problem in polynomial time would be nothing special.)

Just thought I'd ask.

[korona]

Are you sure the algorithm is not pseudo-polynomial?
I.e. the knapsack problem can be solved in O(w * n) time where w is the allowed size of the knapsack and n is the number of weights.
That is NOT polynomial as w depends exponentially on the length of the input (a m-digit number in base 2 can represent 2^m different natural numbers).

[WarDaft]

Also, there's already an algorithm that solves NP problems in polynomial time with a large constant factor iff P = NP, so you need a proof that your algorithm actually solves some NP problem, and never takes more than strictly polynomial time in the size of input.

Note that the size of input of say, 1024 is not 1024, but 10. The size of input 1,073,741,824 is likewise only 30.

[snow5379]

I'm not sure if I should bother responding but... at the moment the program I've written takes 64 integers and returns all possible combinations that add up to 0 in less than a second. I'm planning on eventually modifying the program to take more integers than that. There's a very elegant trick to it all and it's clear as day, knowing the trick, that the program solves problems exactly in polynomial time and doesn't give close approximations.

[WarDaft]

And you're sure you haven't just re-implemented this?

And there's no particular reason it should need modification for more than 64 integers. More importantly... how big are the integers? I can easily write one that works on 200 numbers in less than a second if they are bounded within a relatively small range.



If you're actually finding solutions in a set of 64 numbers, and you picked those numbers at random, that's solid evidence that you're picking numbers that are too small.

How long does it take if you use 1000 random signed 32 bit integers?

[snow5379]

The integers are randomly generated between around -2.1 billion and 2.1 billion. I could modify it to use longs... I probably should actually.

Anyway If I had to guess around a minute or two. I chose 64 integers because each possible combination has an identification number (they're implied and not stored obviously). I don't check every combination (I rarely check any combinations at all actually) but when I do check a combination it's very fast to turn 101101 into n[0]+n[2]+n[3]+n[5]. Also the vast majority of my calculations are bit manipulations and comparisons of these identification numbers. I don't want to give too much away but it's very elegant.

[tomtom2357]

This sounds just like http://xkcd.com/955/

[WarDaft]

Okay, here's 120 random 101 bit signed integers.

Spoiler:

Code: Select all

448864614106338446876780020767,   271830200042577546900991463377,   -496253014144708767358301538056,   -1137715754479326957169649026080,   
517048710808024164016795771905,   1079047989678220780375281638943,   -11541987021955611334952001311,   -517939199787742113105670416528,   
1185803818900774065793914459847,   216118508922868306765812366903,   649492363932522302716146783863,   -618541004006086744210255924572,   
563309559810074533314155272505,   -902086557521605172160094210215,   907347075088851417444790811535,   -426123441841760570205037631252,   
262654598550810805093445544991,   127913250505269277063505412283,   248451556513610272442033661336,   -525183596467272760782237970652,   
-701968401016881642087915117353,   -831833117274351314027515537298,   -743424503458583776710735173189,   -774631609276617396268340191866,   
-647282560993248675585093462939,   -1102850260776879016680319399714,   -19551268115014620521222492584,   -34123494270093003052874228814,   
670888480316293895844736208555,   784260007933225963692505194331,   -906609477204685639942833979010,   784206862235805308470875990686,   
390257167466768541477832170743,   -751671496012358416716409296219,   620162541612523330778573930151,   63541344877359934668145810673,   
-1077133481277469233950146491331,   -399910652009436422857168400161,   295377425885294687249607357975,   -163009224781062348419151255840,   
-118727733065573878959368156940,   117130766990922076634560284515,   1216290330277827755100382755154,   -675627319039305650789294521601,   
104738696437449235385593738059,   720577749844400956523341405058,   1069832873159085031542039376469,   1118579788597853282946718864727,   
-794797160306470366754993508254,   83584227542966597147837784191,   -804915905369815396651578506321,   -324009211775177869485048536987,   
122397553071388115459696583907,   256836215086507087586308966540,   -682270072785569083672668186753,   363166777169968194356811079942,   
783969685349622141080654745818,   485807605137360001966560219216,   737260613736293888798324731374,   644065281090141880087758364468,   
1003714559896816464873565778731,   722747188352832882470636453099,   685835463411180540736981853551,   268109135504993442726447348081,   
-565479476703824407177513533749,   330961365385778956776420418566,   -460163904183209967512019353176,   306782097643372316888482998969,   
-204609583256242910148802450697,   772106871422529369477104378992,   -1099755993821239896758455243750,   1259726270190026477846273827560,   
934822230508980970375123834611,   -160508227615595043136970813730,   -532146164387199792718890263104,   805336940574235101367726285487,   
-918261125353741506452425437849,   606713050095104535361460297389,   754392266146066016583354773515,   5815665667767665068142386078,   
-1016544610625666367199190607993,   1106612985733044330283028269816,   546362197359360834888414495236,   -610316333274492399795217801486,   
-905810224149207026903981471292,   -622808053791617204932363994740,   -833984104291496188504138708042,   567484454044405475308443731029,   
526040927355095746031404873469,   723561744292577895200781125970,   965629394307004871386819844375,   592336702837917088420067374867,   
-324801726279191110490197424465,   -372009100708452555023261819063,   1132221097166864496321621959470,   624181525009413304447597584522,   
230576473180254550289843120464,   265610839857324739165354622976,   -854141104886894245736676182062,   -309717801149313130730641791131,   
-189375311737128892543044316204,   585674652035997485281527238530,   678121977336101694262648540188,   1135310877726340991029179277726,   
840978537271740617460118313746,   -42104692798588843283411920637,   -494559673371725031420023563341,   725472501671285178439144676327,
-398565828751372455533535518021,   1127597256407338894705930103937,   582713678682635321269365703090,   -824170902879999909325584706040,
26618829899865557856332075140,   172832357261654709097390663381,   905696799899102837706643887336,   329441820985400480100296979393,
442459529180504670864498831384,   670619472014575224264869604438,   -527625090711436048727574615677,   212740328760369571331789108961

Does it have a solution? Probably, there are more elements than the size of the numbers. If it does, you should be able to provide a solution if your algorithm truly is polynomial.

Note "you should be able to provide a solution if your algorithm is polynomial" rather than "your algorithm should be polynomial if you are able to provide a solution."

[snow5379]

Uh... all those numbers are about the same length. If you gave me the numbers in sorted form and padded with 0s I could probably solve that in my head. Classically the subset sum problem only takes a long time with certain sets of data. Anyway the issue here is not solving problems but solving them in polynomial time. There are NP complete problems with 10,000 or more objects that have been solved yet no known polynomial time algorithm exists (other than mine I guess).

[letterX]

I believe the idea here is something along the lines of a 'Zero Knowledge Proof'. That is, you've made a claim, that you can solve subset sum in polynomial time. We're justifiably skeptical. Similarly, you're justifiably unwilling to release any details about your algorithm, since if it holds up, it's likely worth large amounts of money/other rewards to you.

However, if we send you a number of subset sum problems that we ourselves are unable to solve, and you send us back the answers, we can check that you're solving subset problems much faster than you should be able if P!=NP (or at the very least, you've found a surprisingly efficient but still not polynomial algorithm for doing it). This doesn't reveal anything at all about your methods, but if what you're saying is true, then it should take very little effort to give us back the answer, while still being evidence* in favor of you having a polytime algorithm.

Of course, I totally understand that the average input to an NP complete problem is likely to be easy, but if it's so damn easy, why don't you just give us the answer? Refusing to give evidence to back up your claim, even evidence which reveals absolutely nothing about your method, is just going to make you look like a troll.


* note the distinction between evidence and proof, of course.

[jareds]

Please also note that your algorithm needs to work on arbitrary-precision integers anyway. Solving the subset sum problem for N integers of N bits each needs to be bounded by a polynomial of N^2, which is therefore a polynomial of N, just as solving it for N integers of 64 bits each needs to be bounded by a polynomial of 64*N, which is therefore a polynomial of N. In fact, the hardest instances of the problem will be such medium density instances. If the number of integers is vastly greater than their size, or if their size is vastly greater than the number of them, the problem is much easier.

Finally, I don't understand your implication that the problem is easily solved for sorted numbers of about the same length. It is not difficult to reduce an instance of 3SAT to an instance of subset sum with numbers of about the same length. Regardless of what your algorithm can do, you surely cannot be claiming that you can solve arbitrary instances of 3SAT in your head.

[snow5379]

I was just saying that it would be easier to solve the problem in my head if the problem was given in that form. To a computer it makes no difference. Anyway I understand what you guys are saying and I plan on eventually modifying the program I have written to take more than 64 integers. I've been busy lately with work and such and just haven't gotten to it yet.

I'm not really interested in proving anything to anyone here... I was just asking for information about publishing and I would probably just post a simple proof that P=NP here if there wasn't a reward for such a proof. I'm probably going to modify my program before publishing or just publish the proof without the program because the written proof is so elegant. I actually proved P=NP well before finding an algorithm that does it... the later is much harder than it sounds.

[jareds]

I hope you don't think that journal editors mechanically begin the process of peer review for every submission that they receive. In actual reality, an unsolicited proof that P=NP from a non-expert will not be read by anyone.

Fortunately, possession of an efficient algorithm for solving an NP-complete problem is by far the strongest position for someone lacking any inherent credibility who has resolved the P?=NP question to be in. The process you would follow is as follows:

Convince someone with greater credibility than yourself to let you demonstrate, by solving instances that they provide, that you can solve subset sum. At that point, this person will likely be willing to find a second person, of greater credibility than the first person, who is willing, on the basis of the first person's recommendation, to allow you to demonstrate your ability to them. After a few iterations of this, a prestigious complexity theorist will help you publish your result.

You could probably make a good start on this very forum.

[SeaCalMaster]

I want to clarify something. You're claiming you have an algorithm that

- takes, as input, a set S containing n integers,
- returns a list of all the subsets of S that sum to 0, and
- finishes in time that is polynomial in n for all S.

Is this a correct characterization?

[WarDaft]

If the number of integers is vastly greater than their size, or if their size is vastly greater than the number of them, the problem is much easier.

Easier than the size of only one of the two would indicate, right? That is, doubling the number of numbers should not make it significantly easier (though it does leave you far more confident that there is a solution) but obviously only doubling only one aspect leaves you with a substantially easier problem than doubling both. I'm not that familiar with the various classes of solutions to the problem.

I was just saying that it would be easier to solve the problem in my head if the problem was given in that form.

Then sort them and solve it in your head.

You cannot honestly expect us to believe you have created a poly time solution to an NP complete problem and yet are unable to sort a list of numbers.

[korona]

Could you give us an upper bound for the time complexity of your algorithm?
Random 3-SAT instances with n=200 variables and m = 4.5 * n clauses can be easily solved by state-of-the-art SAT solvers in less than 0.1 seconds.
The standard transformation from 3-SAT to SUBSET-SUM is O(size^2). Using the parameters above we would get an instance of SUBSET-SUM with 2.200 numbers and 1100 digits per number.
If your algorithms upper bound is a polynomial of a low degree (e.g. O(n^5) or lower) you should be able to solve that instance within a few minutes as a sat solver needs less than 0.1 seconds and the transformation is only O(size^2).

[jareds]

If the number of integers is vastly greater than their size, or if their size is vastly greater than the number of them, the problem is much easier.

Easier than the size of only one of the two would indicate, right? That is, doubling the number of numbers should not make it significantly easier (though it does leave you far more confident that there is a solution) but obviously only doubling only one aspect leaves you with a substantially easier problem than doubling both. I'm not that familiar with the various classes of solutions to the problem.

Sorry, I meant that, for any given input size (i.e., the total number of symbols in the formal input, provided you are using a sane input encoding such that it is directly proportional to the sum of the logs of the numbers), if the number of integers is vastly greater than their size, or if their size is vastly greater than the number of them, the problem is much easier than if the number of integers is similar to their size. E.g., one million 100-bit integers or one hundred 1,000,000-bit integers is much easier than ten thousand 10,000-bit integers. Hopefully, this is clear.

My basic point was to ensure that snow5379 understood that the algorithm must be polynomial in logarithm of the numbers as well as in the number of numbers.

[WarDaft]

Yes, okay, that's equivalent to what I was going for.