Polynomial time factoring algorithm using Bayesian arithmetic

http://arxiv.org/abs/1212.4969

by danpalmer • 14 years ago

19 14 14 years ago

arxiv.org

jellyksong• 14 years ago

The abstract states, "When applied to NP-complete algorithms, this leads to the fundamental conclusion that P = NP".

Isn't this a much more important conclusion?

danpalmer4• 14 years ago

Yes, this is the implication of the paper, although it may be a bit of a jump from the main focus which is a little simpler.

jmurley• 14 years ago

Agreed. Lots of papers like this are submitted, but none have been right so far. Is there some reason to trust this one in particular? I'm not sufficiently familiar with this material to evaluate it.

danpalmer4• 14 years ago

This happened a few years ago when someone posted some code on GitHub that they claimed demonstrated P=NP, however it turned out not to.

This paper on the other hand is a more theoretical approach and appears to be more concrete than previous attempts that I'm aware of.

While it may or may not be correct, (experience hinting at the latter) it is interesting news, and an interesting paper nonetheless.

bzax• 14 years ago

You might as well start with his proof of P=NP

http://arxiv.org/pdf/1205.6658.pdf

ColinWright3• 14 years ago

OK, I've really only skimmed it, but here's an impression ...

He spends a huge amount of time setting up the very very specific equations, and then waves a magic wand saying "This is a Linear Programming Problem which can be solved in polynomial time."

It looks to me like an integer linear programming problem, and that's known to be NP-Complete. There doesn't seem to be anywhere that he takes a non-integer solution and converts it in polynomial time to an integer solution (or provably fails), nor is there anywhere that shows how to find an integer solution in among all the possibly exponentially many solutions it might produce.

danpalmer4• 14 years ago

Not sure if this helps, but this paper shows that Integer Linear Programming is solvable in 'pseudo polynomial time' when dealing with fixed constraints - http://lara.epfl.ch/web2010/_media/papadimitriou81complexity...

ambrop7• 14 years ago

which essentially means it needs exponential time, and as such is useless

nate_martin• 14 years ago

According to wikipedia Integer Programming is NP-Hard http://en.wikipedia.org/wiki/Integer_programming

danpalmer4• 14 years ago

As far as I understand from the two papers, and I haven't finished reading them, nor do I expect to understand it all, but this appears to be very much an LP problem, not ILP, from what I've read so far.

ColinWright3• 14 years ago

I don't have time now, and I'm unlikely to have time in the next six months, but it looks awfully like he's setting up a standard LP problem, but I don't see how he's extracting integer solutions from it.

I expect there to be errors, and I expect them to be subtle, and I expect that if they're pointed out he'll push them around to some other place where they're hard to find. Having said that, I haven't read it thoroughly (and won't have the time to) and I'm disinclined to. Not that that's any great loss - I'm not an expert.

gizmo686• 14 years ago

When I opened this page, I was going to be the third comment, then I got caught up trying to explain why their linked paper [1] (proving P=NP) is non-sense. Unfourtuantly, my habit of assuming that my not understanding something just means that I need to re-read it or play with that segment of the proof myself costed me more time than I thought (even after I wrote in my partially completed reply that the introduction alone was sufficient to dismiss the paper as nonsense). Anyway, here is my overkill analysis:

I would be highly skeptical of their claim. First of all, if they did prove P=NP (and long enough ago to write another paper), then I cannot imagine why this is the first I am hearing about it, as solving this problem would likely get a prominent spot in mainstream news, and definitively its own article on HN.

Beyond that, the paper proving P=NP, even to my amateur eye, looks like garbage. From the P=NP paper: "What is the powerful ingredient which allows a dramatic speed-up of quantum computation over classical computation ? We propose that this ingredient is an implicit use of the Bayesian probability theory. Furthermore, we argue that both classical and quantum computation are special cases of probability reasoning. On these grounds, introducing Bayesian probability theory in classical computation as well, we reduce a typical NP problem, namely 3-SAT, to a linear programming problem. According to algorithmic complexity theory, this proves that P=NP."

"Any logical algorithm can be formulated as a linear programming problem. Specially, a basic question of logical satisﬁability with n variables, namely 3-SAT, is equivalent to a linear programming problem with O(n^3) unknowns and even in general with O(n) unknowns. According to algorithmic complexity theory, this proves that P=NP."

"Again, the main reasons of the supposedly quantum eﬃciency are basically unknown, but the common wisdom is that entanglement should be the key ingredient. Indeed, in the quantum community, it is ‘widely believed that classical systems cannot simulate highly entangled quantum systems’ [13]. By contrast, we have nevertheless argued [14] that the concept of entanglement is actually a quite classical attribute of contextual systems. Furthermore, any classical computer can be regarded as a highly entangled system as far as the entanglement is measured between the binary digits of the processed data during the computation. In addition, we shall argue that the crucial ingredient is not in the least a Hilbert space with its full quantum machinery but only a ﬂexible randomization, or to be exact, the implicit use of Bayes probabilities. This is like a grin without a cat in Alice and Bob adventures in Quantum Land."

They devote two pages to history and what should be common knowledge to anyone interested in this paper.

The actual proof is mathametical gibberish, however there are surprisingly large contiguous sections of the proof that, by themselves, work.

[1] http://arxiv.org/pdf/1205.6658v2.pdf

j2kun• 14 years ago

Red flags: a single author, use of nonstandard terms like "algorithmic complexity theory" (the standard term is simply "complexity theory"), appeals to quantum computing theory (which is only tangentially related to the topic of the paper), author only has two papers, no coauthors, and begins with awkwardly irrelevant statements like, "Arithmetic is a part of abstract mathematics."

Polynomial time factoring algorithm using Bayesian arithmetic

Related Stories