8
$\begingroup$

I've always wondered if proofs in computer science would be considered sufficient proofs of the proposition if they needed to assume physical laws?
For example, I'm wondering what would happen if someone someday proved P != NP under the assumption of the second law of thermodynamics. Would this settle the debate of P != NP?
Or would the problem be still considered unsolved if it rests on physical assumptions?

$\endgroup$
  • 6
    $\begingroup$ The second law of thermodynamics has nothing to do with P $\neq$ NP, which is a purely mathematical question. That would essentially be like saying that relativity was needed for a proof of Pythagorean's theorem. $\endgroup$ – Peter Shor Aug 22 '15 at 22:43
  • $\begingroup$ @PeterShor: I don't see why, although it's probably because I just don't know enough to see why. But I feel like intuitively I wouldn't be completely surprised if there was a connection. This is obviously purely hypothetical, but if every bit flip had an associated minimum increase in entropy, for example, then maybe you could use the entropy change from the input to the output to argue that a certain number of bits must have been flipped, which would take a minimum amount of e.g. exponential time. Or something like that, I don't know. Is such a proof completely out of the question? (Why?) $\endgroup$ – Mehrdad Aug 23 '15 at 3:26
  • $\begingroup$ @Kaveh: I don't have an example, but here's a potential one: I think it is reasonable to ask whether an axiom such as the axiom of choice "really" holds in the physical world. Maybe it is, maybe not; maybe we'll never have a way to test it. But we can certainly ask. And if there was a physical way to prove that it does(n't), then that would imply that any theorems based on it are (un)true in the physical world. So if I accept that the aforementioned is a valid question, then it doesn't require a huge leap of faith to ask whether there is such an axiom underlying, say, P vs. NP. $\endgroup$ – Mehrdad Aug 23 '15 at 3:39
  • 6
    $\begingroup$ In your comment above, I think you're confusing two different things: the use of ideas derived from physical laws in mathematical proofs, and the use of the actual laws of physics in mathematical proofs. For instance, there are lots of mathematical proofs that use the mathematical definition of entropy; however, this mathematical definition exists and is useful independently of whether or not the laws of thermodynamics are true in physics. Another example – we can use Euclidean space in mathematical proofs, despite the fact that actual physical space is curved and not Euclidean. $\endgroup$ – Peter Shor Aug 23 '15 at 13:36
7
$\begingroup$

It seems at least possible to me, but currently very unlikely. To sum up the below, it's because the current mathematical statement of (say) P vs NP is completely independent of any laws of physics, so one would need to describe new models of computation that do depend on physics axioms.

The key point that Peter Shor made in his comment is that CS theory questions, such as P vs NP, refer to very simple and stylized mathematical models. They aren't statements about the real world. They just say "in this mathematical model, ___ is true".

Now, one does often have empirical laws, such as the Church-Turing thesis, that state that the real world acts like these mathematical models. But that's a one-way connection (it doesn't mean that mathematical models must act like the real world!). To flesh out Peter Shor's example, the Pythagorean theorem only needs the ideas of real numbers and the Euclidean plane/distance. The model is much simpler than the real world and doesn't involve e.g. gravity, electromagnetism, thermodynamics, etc. And even if the Pythagorean theorem were sometimes false in reality because of these complications, this would not affect its mathematical truth.

Similarly, the model for the Turing machine and the definitions of P, NP, etc are much simpler than the real world. The model does not involve things like gravity, thermodynamic entropy, etc. The truth of P vs. NP does not depend on whether computation can actually happen efficiently in the real world.

Now, it seems to me hypothetically possible that in the future, we could discover closer connections between laws of physics and laws of computation. What would happen then is that the mathematical model of the Turing Machine would have to be expanded to account for these connections. One would then have to formulate new definitions of P and NP for this new model and argue that these are "better" than the old model and definitions. Then, in this new physics-aware model, one could have physics axioms that are used in proofs. But this seems very unlikely / far from happening, at least to me.

$\endgroup$
  • 4
    $\begingroup$ If we revise models and change P and NP, it would not be what we refer to as "P vs. NP" any more, it would be a different question. We already know P is not equal to efficiently computable in practice. The reason we keep P is because it is a useful simplification not that it captures reality of computation in practice. $\endgroup$ – Kaveh Aug 23 '15 at 19:45
  • $\begingroup$ To be fair we also don't even know if it's impossible to build a non-deterministic turning machine. Or a PostBQP machine. The weird part is that when we prove things about the models of computation we can create, we can say things about those models that some see as more "true" because they apply to real things. But we equally study algorithms with no feasible run-time or models of computation that can never be realized in practice, because whether or not the models themselves can be realized is independent of what we can prove about them. $\endgroup$ – Phylliida Aug 26 '15 at 22:54
5
$\begingroup$

I like the question… but the answer is still "no", as other contributors have indicated. The question itself is metamathematical, which is why I like it.

Mathematics and physics are different epistemological universes, and never the twain shall meet. A mathematical universe is constructed of 1) definitions (like the integers) 2) axioms and 3) rules from contracting new true statements from known true statements (like Modus Ponens, which dictates that A->B and A together imply B). Physical objects have no entry into such universe.

The physical universe is matter -- and, as Schopenhauer said, matter is causality and causality is matter. Mathematical objects and proofs do not have any impact as such on the physical world (though there can be impacts of people believing in mathematical claims and their proofs). Science consists of systems that describe, more or less faithfully, observable phenomena of the physical world. I think Karl Popper captured this epistemology best in his theory of empirical falsification. Science utilizes mathematics in its descriptions, but science is not itself the phenomenal world.

Natural phenomena do not have to obey our mathematics, and our mathematics cannot be proved true or false by the physical world. But it is no accident that mathematics seems to capture aspects of what we observe -- we made it that way. The phenomenal world inspired the definitions that are the stuff of the mathematical universe.

It is not so surprising that this question arises in computer science, since the computer is the ultimate physical object for mimicking the mathematical world.

$\endgroup$
1
$\begingroup$

For example, I'm wondering what would happen if someone someday proved P != NP under the assumption of the second law of thermodynamics.

the premise of the question is research-oriented but somewhat mixed up/ backwards in the following sense. a deep connection between thermodynamics and CS complexity has indeed been demonstrated in the area of "spin glasses" where the process of magnetic orientations settling during cooling closely mimics the phase transition found in SAT, and this connection continues to be explored and is regarded as much more meaningful than merely coincidental.

in a sense computational "hardness" seems to be an "explanation" or basic mathematical model for a fundamental thermodynamic process. also thermodynamics has the proscription against perpetual energy machines but which can also be seen as a general constraint against machines that cannot exceed certain "physical speed limits". if P!=NP then a physical machine that solved NP problems in P time could not exist and would "defy the laws of physics" namely in the "speed" at which it "manipulates information". but many physicists are concluding the laws of physics apparently essentially come down to manipulation of information. so in short, quite possibly the trend is that computational complexity theory will in the future better explain fundamental thermodynamics laws.

more detail, see eg this Phd thesis (2013):

$\endgroup$

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.