Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Macroscopic quantum objects cannot exist if P ≠ NP?

medium.com

Post reply on HN
Print view View original

61–70 of 75 posts

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#61

Post by pcvarmint »

baddox wrote: post #40

> What’s interesting about NP-hard problems is that they are mathematically equivalent. So a solution for one automatically implies a solution for them all. That's a mistake. The author is describing NP-complete problems, which are all roughly equivalent (reducible in polynomial time). NP-hard includes all NP-complete problems, but also includes problems much harder than those in NP-complete, including undecidable pr…

> That's a mistake. The author is describing NP-complete problems...

Correct. I think that quote basically killed the whole article for me.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#62

Post by mdxn »

awhitty wrote: post #52
Dunnorandom wrote: post #15

For anyone interested, here's Scott Aaronson's response to the paper: http://www.scottaaronson.com/blog/?p=1767#comment-103591

I understand that people get a little passionate about their fields of study, but the tone of Aaronson's response is wildly inappropriate. Phrases like "a common novice mistake" and "as if he just emerged from a cave" are unnecessary and entirely condescending. This style of discourse fosters a really awful and exclusive atmosphere, and I wish it wasn't the norm. I don't know this guy at all, and I'm guessing he's pr…

I can see how it can be read that way, though you should also to look at this from his perspective (or at least my guess as to a possible perspective).

The internet (and the field) is flooded with nonsense papers that don't respect the hard work of others. A lot of them really do come from these "common novice mistakes". The authors are taking very superficial views of complexity theory and physics against the advice of researchers in those fields. This particular one hasn't, but a lot of them have incredibly bad and egotistical attitudes. I think researchers see this as incredibly insulting, ignorant, and a severe lack of humility. People aren't showing enough respect and care to this field.

This wouldn't be such a problem if it didn't happen more often than not. On top of that, these poor findings end up swarming around the media and dilute the field. Look, Aaronson is a well known guy who has spent a lot of time trying to point out and explain these mistakes. Though people, including pseudo-scientists, completely ignore him. They even start fights with him. He and others get spammed with this stuff weekly if not daily. For him, I bet it's simply too much to ignore.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#63

Post by soganess »

awhitty wrote: post #52
Dunnorandom wrote: post #15

For anyone interested, here's Scott Aaronson's response to the paper: http://www.scottaaronson.com/blog/?p=1767#comment-103591

I understand that people get a little passionate about their fields of study, but the tone of Aaronson's response is wildly inappropriate. Phrases like "a common novice mistake" and "as if he just emerged from a cave" are unnecessary and entirely condescending. This style of discourse fosters a really awful and exclusive atmosphere, and I wish it wasn't the norm. I don't know this guy at all, and I'm guessing he's pr…

I find the dismissive tone and holier and thou attitude that Aaronson has garnered more that bit of notoriety for really detrimental to the growth of both our collective understanding of QM and our understanding of computability. if knowledge is truly power, lording your knowledge over a peer is paramount to oppression. A bit dramatic, of course, but not completely without warrant.

This maybe a bit of a kumbaya, everyone hold hands argument, but I'm going to make it. Its not as if the number of people that have the ambition to collect the wealth of knowledge required to characterize(even incorrectly) any perspective overlap between computation and quantum is exactly a huge working set. I don't consider it reasonable to shit on someone's work so indiscriminately in this space where its rather hard to be right and quite easy to be wrong.

Prima facie, the paper was accepted for publish in a peer reviewed journal (Physical Science International Journal), and. from all the terse looks of it I've encountered, is likely erroneous on a fundamental level. Highlighting this is not meant to imply that peer-review is a good/bad measure of academic muster, but rather an indicator of how complex comprehending and qualifying such theories might be.

My point is, even in its incorrectness, a bravo for thinking so wildly is likely in order.

Disclaimer: I'm a quantum chemist and computer scientist. I'm also not the biggest fan of Scott Aaronson, so I might be harder on him that is likely deserved.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#64

Post by baddox »

pcvarmint wrote: post #61
baddox wrote: post #40

> What’s interesting about NP-hard problems is that they are mathematically equivalent. So a solution for one automatically implies a solution for them all. That's a mistake. The author is describing NP-complete problems, which are all roughly equivalent (reducible in polynomial time). NP-hard includes all NP-complete problems, but also includes problems much harder than those in NP-complete, including undecidable pr…

> That's a mistake. The author is describing NP-complete problems... Correct. I think that quote basically killed the whole article for me.

It didn't kill the whole article for me, although it seems to be a consistent misconception rather than an isolated typo. To be fair, the naming convention is pretty tricky, considering NP-hard contains things outside NP.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#65

Post by baddox »

scott_s wrote: post #59
baddox wrote: post #58

Earlier quoted context omitted.

I've never read any explanation of the Universe-as-a-simulation concept that I have understood. If the Universe isn't a simulation, then what is it?

I don't know - but answering a question with "I don't know" does not imply that we should pick an answer just because we don't have a good answer.

I think it's pretty important to convey or at least have a clear definition of the concept of the Universe being a simulation.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#67

Post by icodestuff »

baddox wrote: post #64
pcvarmint wrote: post #61

Earlier quoted context omitted.

> That's a mistake. The author is describing NP-complete problems... Correct. I think that quote basically killed the whole article for me.

It didn't kill the whole article for me, although it seems to be a consistent misconception rather than an isolated typo. To be fair, the naming convention is pretty tricky, considering NP-hard contains things outside NP.

And the diagram did get the terminology right. The author may need a (better) proofreader, but it wasn't impossible to see what the author meant. They only conflated the names, not the concepts.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#68

Post by todd8 »

nanofortnight wrote: post #56
raverbashing wrote: post #6

I'm not buying it 1 - P=NP is a mathematical problem. It has nothing to do with Physics. Physics has to do with Mathematics but one should be very careful when extrapolating (range, constraints, etc). 2 - Nature has no problem whatsoever solving complicated equations. Our mathematical models are the ones who suffer to model simple everyday stuff in Physics. Turbulence and Navier-Stokes equations, electromagnetic prop…

> P=NP is a mathematical problem. It has nothing to do with Physics. There are some who would disagree with you. It is quite arrogant to assert that computer science has little to do with physical reality when our constraints on computational capabilities are very much embedded in reality. Take a look at this survey article, for instance: http://www.scottaaronson.com/papers/npcomplete.pdf

Thank you for the reference to the Scott Aaronson's paper, and to casual HN readers of this thread, I can't recommend this fascinating and easy to understand presentation enough.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#69

Post by dllthomas »

baddox wrote: post #46
raverbashing wrote: post #6

I'm not buying it 1 - P=NP is a mathematical problem. It has nothing to do with Physics. Physics has to do with Mathematics but one should be very careful when extrapolating (range, constraints, etc). 2 - Nature has no problem whatsoever solving complicated equations. Our mathematical models are the ones who suffer to model simple everyday stuff in Physics. Turbulence and Navier-Stokes equations, electromagnetic prop…

> 1 - P=NP is a mathematical problem. It has nothing to do with Physics. I don't know if I accept that, although it's unclear what exact definitions you're using for those terms. P=NP makes very real claims about the abilities of real physical objects like Turing machines. It's obviously about math as well, but I don't see how that precludes it from being about physical qualities of physical systems. > 2 - Nature has…

"the abilities of real physical objects like Turing machines"

Or at least any physical approximation of theoretical constructs like Turing machines.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#70

Post by dllthomas »

baddox wrote: post #57
IanCal wrote: post #39

Earlier quoted context omitted.

With 2, are you saying there are situations in nature that can solve NP-hard problems in polynomial time? Because if so, we could just use those to solve our hard problems and therefore P=NP. P=NP is not just statement about difficult problems or big equations, it's a very particular class of problems.

Technically P=NP is just about Turing machines (and thus all Turing complete systems, which includes all the computers humans have produced). As far as I know there is no evidence of real super-Turing systems, but the concept has been theorized. http://en.wikipedia.org/wiki/Hypercomputation

Right. "There exists a device that can solve NP problems in P time" is a different statement than "P=NP".

Regarding "Hypercomputation" in particular, I've typically encountered it in the context of "solving problems a TM can't solve" rather than "solving problems a TM can solve but asymptotically faster" - is it actually used for both? A skim of the article didn't clarify.

Post reply on HN