Polynomial time factoring algorithm using Bayesian arithmetic
arxiv.org
arxiv.org
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.
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.
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.
Isn't this a much more important conclusion?
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.
There's no concrete indication that I've found in this paper about how to solve those equations.