Breaking np-complete with memcomputing. Is it real? | Hacker News Reader

Breaking np-complete with memcomputing. Is it real?

meanderful.blogspot.com

15 pointsmhurd17 comments

> 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.

Thanks.

No, for the reason outlined by Aaronson in [0] - I don't see anything in the update which addresses this.

[0] http://www.scottaaronson.com/blog/?p=2212

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.

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.

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.

Yes. That is right. I misunderstood Scott. He makes sense. BQP covers factorisation which is different to NPC.

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.

> 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"?

"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].

[1]: http://www.amazon.com/Quantum-Computing-since-Democritus-Aar...

[2]: http://www.scottaaronson.com/democritus/ , see "Lecture Notes" section.

Yeah, exactly right. Not all opinions deserve to weighted equally.

Thanks. I'll have a read.

>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")).

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.

There could turn out to be a tractable algorithm for some NP-complete problems, but when you do the reduction, it expands and is no longer tractable. There are also other ways in which different NP-complete problems are meaningfully different. See https://cstheory.stackexchange.com/questions/24879/easier-an... for some discussion. Look also at the first page of http://people.orie.cornell.edu/shmoys/or630/notes-06/lecture...

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.

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.

I do appreciate the education I received :-)

No. Grab a copy of Ja Ja's book. There are some cool things you can do with a PRAM machine. http://www.amazon.com/Introduction-Parallel-Algorithms-Josep...

Reply on news.ycombinator.com