Polynomial time factoring algorithm using Bayesian arithmetic(arxiv.org)
arxiv.org
Polynomial time factoring algorithm using Bayesian arithmetic
http://arxiv.org/abs/1212.4969
5 comments
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.
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.
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.
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.
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.
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...
which essentially means it needs exponential time, and as such is useless
According to wikipedia Integer Programming is NP-Hard http://en.wikipedia.org/wiki/Integer_programming
You might as well start with his proof of P=NP
http://arxiv.org/pdf/1205.6658.pdf
http://arxiv.org/pdf/1205.6658.pdf
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?
Isn't this a much more important conclusion?
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.
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.
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.
Actually, there appears to be nothing new, structurally or ideas-wise, and I don't think it is very interesting. The concreteness is all about creating a system of equations in terms of the bits in a multiplication. That's really trivial. Large and messy, but nothing new.
There's no concrete indication that I've found in this paper about how to solve those equations.
There's no concrete indication that I've found in this paper about how to solve those equations.
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.
[deleted]
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."
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 satisfiability 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 efficiency 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 flexible 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