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.
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.
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.
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.
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 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.
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."
15 comments
[ 3.1 ms ] story [ 50.7 ms ] threadIsn'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.
http://arxiv.org/pdf/1205.6658.pdf
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.
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