[raverbashing]

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 propagation, the way lightning goes through the air, etc.

[swombat]

Unless, of course, our entire reality is running on a very powerful, but not infinitely powerful computer, and the Great Programmers in the Sky decided to cheat by putting in a hack that cuts off quantum behaviour at a larger scale...

Unlikely, but cute...

[cstross]

Or

The granularity of the simulation of our reality is the Planck length. This constraint does not apply to the real, underlying, reality within which our simulation is embedded.

[nemo1618]

http://www.simulation-argument.com/

[sk8ingdom]

Relevant xkcd: http://xkcd.com/224/

[baddox]

> 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 no problem whatsoever solving complicated equations.

Solving some complicated equations, no doubt. But I'm not aware of any evidence suggesting that nature can easily solve all complicated equations.

[dllthomas]

"the abilities of real physical objects like Turing machines"

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

[nanofortnight]

> 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

[todd8]

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.

[denim_chicken]

There is no evidence that nature can globally solve NP-hard problems. At best, nature finds locally optimum solutions to these problems.

[trhway]

>There is no evidence that nature can globally solve NP-hard problems.

There is no evidence that nature has NP-hard problems. All the nature is built on local interactions - thus the finite speed of any interactions in the nature.

Note: the only example of non-local optimization (specifically maximizing entropy over time-space existence path of a living object vs. that would be an entropy change associated with the equivalent amount of non-living matter in similar environment) is the life itself.

[IanCal]

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.

[scott_s]

There are situations in nature where our models are NP-hard. Whether or not this is the same as saying that nature itself performs those computations is, I think, tied into the question of whether or not our Universe is a simulation.

[elektronjunge]

If natures models reduce to our NP-hard models which they would if our models are accurate, that is to say if and only if there is some computation that is NP-hard (which means that it is proven to not have a polynomial time solution unless P=NP) that nature can solve in polynomial time and we have proven that P must equal NP.

[scott_s]

Our models are not (necessarily) nature. The map is not the territory.

[baddox]

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?

[scott_s]

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.

[baddox]

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

[baddox]

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

[dllthomas]

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.

[baddox]

That's a good point. The first sentence of the Wikipedia article says "Hypercomputation or super-Turing computation refers to models of computation that go beyond, or are incomparable to, Turing computability." The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to. :)

Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster.

[dllthomas]

'The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to.'

I totally agree, which is part of why the article didn't clear it up.

"Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster."

A Zeno machine, for sure. It is not immediately clear to me that this necessarily holds for anything that can solve the halting problem - what about a TM plus a halting problem oracle that would tell you in 2^(size of TM) whether a TM halts?

Of course the real question is whether asymptotically faster is enough to be "hypercomputation". Necessity is also interesting, but not the same thing.

[kang]

Your comments are non-constructive. This second point was almost religious.

To say that a mathematical problem has nothing to do with physics would not be right, since physics' major theories of today are essentially maths.

[scott_s]

For the record: I consider raverbashing's comments constructive. He/she is honestly engaging with the material and other people. The second point is similar to one several people have already made on the thread.

[raverbashing]

"To say that a mathematical problem has nothing to do with physics would not be right, since physics' major theories of today are essentially maths."

No

Physics depends on mathematics, not the opposite.

Math exists regardless of physics.

[mdxn]

This is overly general. And we need to make a distinction between actual physics (laws of Nature) and our theoretical models of such.

Yes. Our theoretical models of the laws of physics are usually formal and axiomatic systems of logic (basically mathematics).

Yes. We understand and describe it using mathematical constructions we know of.

However, the laws of Nature do govern what kinds of models of computation are realizable (theoretically and physically). Limits on computability influence the design and sophistication of logic and mathematics. A good model of computation that we choose for this is some variant of a Turing machine. If this is true for our brains as well, then there is a limit on how sophisticated and powerful mathematics can be from our perspectives. In other words, the laws of Nature are dictating how good of a system of mathematics we come up with can be from a logical standpoint.

[kang]

yes. now i realize.