2

This one has been busting my brain for quite a while now. As far as physics currently tells us, we live in a world where the physical laws are inductive but not deterministic, because at some underlying level there's what we believe is true randomness.

So let's imagine a world where everything is perfectly deterministic, there's no underlying randomness. Therefore every physical process can be solved by a deterministic algorithm exactly every single time. In such a world, does P = NP? If we can conceive of such a world, does P = NP? Or are the two concepts of determinism in computer science and physics not related at all? There's gotta be at least some connection. Please no one-word answers, I want some insight here.

| improve this question | |
6

Abstract mathematics doesn't have to be related to physics. There are many things that mathematicians routinely consider (such as non-measurable sets, etc) that cannot possibly exist in the physical world.

In particular, the laws of the physical world have no bearing on the P=NP problem.

| improve this answer | |
  • 1
    To add to this, the nondeterminism used in computational complexity theory is mathematically defined. The question of whether the class P is the same as the class NP is a mathematical one. It is decidable by mathematical considerations alone. A deterministic algorithm for a problem in NP might take provably exponential time (or might not, we don't know yet because there's no mathematical proof!). – Mitch Jan 4 '14 at 16:49
  • I'm not sure your last sentence is correct; computability is an abstract idea, while practical computability is determined by the physical laws we know about. Whether or not P = NP does seem to say something about physical reality. Consider the power of the human brain: does it solve NP-complete problems? We just don't know yet; if it does, that's pretty interesting. If it doesn't, does it always find a way to 'cheat' by taking into account domain-specific information to move the problem to P? Are all the 'interesting' questions somehow reducible to less-than-NP, or small enough in size? – labreuer Jan 8 '14 at 16:22
  • @labreuer, you are assuming human brain powers that it may not have. True, many interesting problems, including the ones addressed by our brains, are NP-hard, but who told you that we are good at find solutions to them? More often than not an approximate solution suffice for practical purposes, and many NP-hard problems have P approximations (although not all of them do). Moreover, for practical purposes it's sometimes sufficient to be "significantly more often right than wrong", and this makes complexity class BPP more relevant than P. – Michael Jan 8 '14 at 16:35
  • @Michael, very true. Maybe all interesting NP-complete problems have good enough approximations once all domain knowledge is utilized. The statement that physics and computation are entirely separate, though, seems specious to me. If future physics work can inform theory of computation, I'd claim that there is some kind of connection. I offered an answer to this question that fleshes out my position a bit. – labreuer Jan 8 '14 at 16:42
  • @labreuer: not all NP-complete problems have approximation, that follows from PCP theorem. Regardless, non-determinism in complexity theory doesn't mean exactly the same as in philosophy; that makes P v. NP problem less relevant to physics. – Michael Jan 8 '14 at 16:53
3

A deterministic universe might not be a quantum universe, in which case algorithms like Shor's algorithm would be impossible; whether there will be a quantum or post-quantum method for solving NP problems in P-time is unknown. Suppose that there is. This won't mean that P = NP; Shor's algorithm is in complexity class BQP: bounded error quantum polynomial time.

The NP complexity class is a different kind of non-deterministic than our current knowledge of quantum mechanics and its non-deterministic nature. We know this because no known quantum computer can solve NP-complete problems in polynomial time. This is because to solve NP-complete problems in P-time, you would need to be able to spawn n – 1 new instances of the program at every decision point with n possible decisions. It's not quite "trying everything simultaneously", but it's close. No known quantum computer can "try everything at once"; this is because quantum circuits aren't 'powerful enough'.

Suppose that we find a new kind of quantum computer that can solve NP-complete problems in P-time. Whether or not the universe had to be this way will probably be a matter for philosophers. But surely you can see that in a deterministic universe, that quantum computer [probably] wouldn't be available. So if you create a digital world populated by sentient beings and make that world deterministic, those beings probably won't be able to compute as much as you can in any given time period.

All this being said, it could turn out that classical computers can be used to solve NP problems in P-time, if it ends up that P = NP. In that case, whether or not the world is deterministic or indeterministic would be utterly irrelevant. At this point, we just don't know. If you want your mind blown with respect to computation and physics, see this primer on black hole computation, and then head over to Scott Aaronson's discussion of recent firewall controversies. "What is realistically computable in our universe?" is a fascinating question. Maybe there is a deep link between computation and physics!

| improve this answer | |
1

The question whether P=NP has no bearing on whether processes are deterministic are not, only on the relative amount of effort that deterministic vs. nondeterministic stepwise processes may take to arrive at solutions to particular types of problems. The nondeterminism considered is always limited to a finite, enumerable choice of alternatives, so for any of the nondeterministic processes considered, a deterministic 'equivalent' always exists (e.g. obtained by exhaustively trying out all alternatives in some systematic way).

| improve this answer | |
0

In simple words what Michael says is that the questions of mathematics (such as P=NP) do not relate to the properties of any physical world. Physics use and develop mathematics, mathematics does not take physics observations or insights as input.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.