Re:Breaking np-complete with memcomputing. Is it real?
by krcz on Thursday July 09, 2015 @08:04AM
(#9857349)
> If we solve NP-complete efficiently then we may break TSP and all sorts of magical optimisation problems joyously drop out of the sky at our feet. It is not clear if this would also break integer factorisation and thus RSA, but perhaps it might.
Not true. Factorization is NP, so having a fast way of solving NP-complete problem would yield a way to solve factorization as well.
On the contrary it is not known to be NP-complete (and is believed to not be), so solving factorization in polynomial time would not help with other NP problems.
Re:Breaking np-complete with memcomputing. Is it real?
by mhurd on Thursday July 09, 2015 @08:13AM
(#9857377)
Interesting. I'm inclined to agree but I pause when I read that Scott Aaronson still seems to hold the line on quantum computing not doing anything too useful for NP-complete or a useful subset. The weight of opinion seems against him on quantum though he remains empirically correct for the foreseeable future.
Re:Breaking np-complete with memcomputing. Is it real?
by jerf on Thursday July 09, 2015 @08:58AM
(#9857546)
"The weight of opinion seems against him on quantum though he remains empirically correct for the foreseeable future."
Then you're misjudging the weights "for" and "against" him by putting way too much weight on people who don't know what they're talking about and way too little on those who do. It is likely that your "for" group are still operating under the idea that "quantum" works by "trying all possible answers then returning the correct one". This is empirically, mathematically-provably wrong. Anyone operating under this idea deserves for you to weight them at zero.
Despite the fact we still can't build a very big quantum computer, we actually do know quite a bit about what they can do and not do. And as Scott Aaronson points out very frequently, if in fact they prove either able to do something our current theories say they can not or unable to do something that our current theories say they can, either way that will be very interesting, precisely because it will imply that there is something wrong with quantum mechanics, which for all its "woo woo" reputation is one of the most solid math-to-reality theories we have ever had in the history of mankind.
Scott Aaronson isn't "holding" the line... he and his fellow-travelers are drawing the line.
Edit: I'm also unsure on why you think Aaronson believes quantum "won't work"... he's on the optimist side that quantum computers can be made practical. If you mean that he doesn't think "quantum" can solve NP-completeness, well, of course he doesn't... he understands the mathematical proof that it doesn't, so that's hardly surprising.
Edit edit: A positive followup to this negative message: Consider reading Quantum Computing Since Democritus [1], or if you don't want to spend the dough, read through the class notes that turned into that book [2].
Re:Breaking np-complete with memcomputing. Is it real?
by ikeboy on Thursday July 09, 2015 @09:30AM
(#9857720)
>If you mean that he doesn't think "quantum" can solve NP-completeness, well, of course he doesn't... he understands the mathematical proof that it doesn't, so that's hardly surprising.
There's no proof BQP ≠ NP (as well as no proof it does).
Scott thinks it doesn't, but doesn't have a proof (if he did, he'd also have a proof of P≠NP (and showing something implies a resolution of P versus NP is a great proxy for "it's not easy and hasn't been solved yet")).
Re:Breaking np-complete with memcomputing. Is it real?
by adrianN on Thursday July 09, 2015 @08:23AM
(#9857408)
Quantum computers can't solve NP complete problems any better than classical computers as far as we know. You can at best hope for polynomial speedups. That is the scientific consensus, I don't know what weight of opinion you're talking about.
Re:Breaking np-complete with memcomputing. Is it real?
by ikeboy on Thursday July 09, 2015 @09:39AM
(#9857767)
He seems to be misunderstanding Scott as claiming that no quantum computers will beat classical ones (even for factoring and the like), whereas Scott only makes the claim for NP-complete problems.
Re:Breaking np-complete with memcomputing. Is it real?
by Strilanc on Thursday July 09, 2015 @08:55AM
(#9857535)
> Scott Aaronson still seems to hold the line on quantum computing not doing anything too useful for NP-complete or a useful subset. The weight of opinion seems against him on quantum
Where are you getting this opinion from? My experience has been exactly the opposite. Could you back it up by referencing examples of this "weight of opinion"?
Re:Breaking np-complete with memcomputing. Is it real?
by cousin_it on Thursday July 09, 2015 @09:45AM
(#9857797)
There's no such thing as a "useful subset" of NP-complete problems. If you solve one of them, you've automatically solved all of them, because they are all reducible to each other.
Re:Breaking np-complete with memcomputing. Is it real?
by ZoFreX on Thursday July 09, 2015 @09:45AM
(#9857794)
This article says nothing. It waffles vaguely about a number of unrelated topics, adding nothing of value to anything that's been said previously, and critically adding nothing of value to the paper it links to.
I suspect it is on the front page of Hacker News only because no-one else wants to appear ignorant of the topics in question by pointing out that it makes no sense.
Re:Breaking np-complete with memcomputing. Is it real?
by mhurd on Thursday July 09, 2015 @10:47AM
(#9858117)
That's harsh but perhaps fair. My little blog post does represent a fair amount of ignorance on my part and I too wonder why it got to the HN front page.
Not true. Factorization is NP, so having a fast way of solving NP-complete problem would yield a way to solve factorization as well. On the contrary it is not known to be NP-complete (and is believed to not be), so solving factorization in polynomial time would not help with other NP problems.
[0] http://www.scottaaronson.com/blog/?p=2212
Then you're misjudging the weights "for" and "against" him by putting way too much weight on people who don't know what they're talking about and way too little on those who do. It is likely that your "for" group are still operating under the idea that "quantum" works by "trying all possible answers then returning the correct one". This is empirically, mathematically-provably wrong. Anyone operating under this idea deserves for you to weight them at zero.
Despite the fact we still can't build a very big quantum computer, we actually do know quite a bit about what they can do and not do. And as Scott Aaronson points out very frequently, if in fact they prove either able to do something our current theories say they can not or unable to do something that our current theories say they can, either way that will be very interesting, precisely because it will imply that there is something wrong with quantum mechanics, which for all its "woo woo" reputation is one of the most solid math-to-reality theories we have ever had in the history of mankind.
Scott Aaronson isn't "holding" the line... he and his fellow-travelers are drawing the line.
Edit: I'm also unsure on why you think Aaronson believes quantum "won't work"... he's on the optimist side that quantum computers can be made practical. If you mean that he doesn't think "quantum" can solve NP-completeness, well, of course he doesn't... he understands the mathematical proof that it doesn't, so that's hardly surprising.
Edit edit: A positive followup to this negative message: Consider reading Quantum Computing Since Democritus [1], or if you don't want to spend the dough, read through the class notes that turned into that book [2].
[1]: http://www.amazon.com/Quantum-Computing-since-Democritus-Aar...
[2]: http://www.scottaaronson.com/democritus/ , see "Lecture Notes" section.
There's no proof BQP ≠ NP (as well as no proof it does).
Scott thinks it doesn't, but doesn't have a proof (if he did, he'd also have a proof of P≠NP (and showing something implies a resolution of P versus NP is a great proxy for "it's not easy and hasn't been solved yet")).
That said, it is unclear how far Adiabatic notions will take us but it seems there are limits there too with respect to the spectral issues.
Where are you getting this opinion from? My experience has been exactly the opposite. Could you back it up by referencing examples of this "weight of opinion"?
I suspect it is on the front page of Hacker News only because no-one else wants to appear ignorant of the topics in question by pointing out that it makes no sense.
I do appreciate the education I received :-)