Bringsjord says P!=NP implies digital physics is incorrect

[gusl]

http://kryten.mm.rpi.edu/scb.pnp.solved14.pdf

Our argument shows that if P!=NP, digital physics is incorrect. Since it must be true that
all physical phenomena can in principle be modeled in information-processing terms of some kind,
P!=NP thus immediately implies, courtesy of our arguments, that hypercomputational processes
exist in the physical universe. If you believe, as many do, that hypercomputational processes are
always merely mathematical, and never physically real, you can’t be rational and at the same time
refuse to accept our case for P=NP.

Comments

[easwaran.livejournal.com]

They end up saying that the burden of proof is on those who would reject digital physics. However, in mathematics, the burden of proof is always on everyone. So if their argument is right (I seem to remember one or two other steps I found questionable), all they've done is shown that "digital physics" is equivalent to P!=NP. But I'd say people are in general more confident of P!=NP than they are of digital physics.

[spoonless.livejournal.com]

I just read it... and I noticed you switched the not-equals signs to equals signs in that paragraph! (Unless there's some weird thing with the font in lj that I'm not seeing). The pdf version says "Our argument shows that if P != NP, digital physics is incorrect." etc.

If their argument is solid, then this might be good reason to believe in continuous physics over discrete physics. Or perhaps it's a reason to believe P=NP. But my first guess would be that they're hole "bucket of soap" argument is full of a few holes.

[gustavolacerda.livejournal.com]

oh you're right, thanks... the not's had turned into boxes, so I deleted them.

[spoonless.livejournal.com]

I read the part about the bucket of soap a bit more carefully, and I think they're full of crap.

I don't assume that physics is "digital" or continuous, I think that's yet to be determined. But even if it's digital as Wolfram and others think, I don't buy their soap argument for P=NP.

They say that the soap film solves the problem for small N in polynomial time. This may be true, but it does not imply that there is a way to scale this up so it will solve it for large enough N to be useful, let alone for infinite N which is what they need for their proof.

They use a pseudo induction argument on N saying "if it works for N, then surely it'll work for N+1". But this does not work for physics. If you applied that to dividing matter into parts, then it would lead you to an inductive "proof" that matter is infinitely divisible... you can divide it in half N times, so why not N+1? The problem is, eventually you move into another regime where things work differently. In the case of the soap film, your nails are going to get too heavy for it to still solve the problem at some point... or you'd have to make them so small that they'd need to be tinier than an atom. There's all sorts of ways their argument could fail here. And I would be willing to bet that it does. In fact, somebody should offer a $million prize for whoever can get a soap-film machine working that can solve NP complete problems in polynomial time. I'll believe it when I see it! Till then, I think it's wishful thinking on their part.