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