{\huge Theorems From Physics?}

Can information physics extract proofs from reality? \vspace{.5in}

Rolf Landauer was a physicist and computer engineer who spent most of his career at IBM north of New York City, becoming an IBM Fellow in 1969. According to his longtime colleague Charles Bennett, Landauer ``did more than anyone else to establish the physics of information processing as a serious subject for scientific inquiry.'' One was was his discovery and formulation of a principle connecting non-reversible computation steps and thermodynamic entropy, which according to Wikipedia's article is widely accepted as a physical law.

Today Ken and I want to talk about the possible role of physical laws in generating proofs of complexity assertions, even $latex {\mathsf{P \neq NP}}&fg=000000$ itself.

Recently we have heard of interest connecting $latex {\mathsf{P \neq NP}}&fg=000000$, and the related topic of one-way functions, to Landauer's principle itself. According to Bennett again, Landauer's principle states:

ny logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computation paths, must be accompanied by a corresponding entropy increase in non-information bearing degrees of freedom of the information processing apparatus or its environment.

Bennett has defended this assertion against various objections. Last year a team from the \'Ecole Normale Supérieure de Lyon, the University of Augsburg, and the University of Kaiserslautern gave empirical support by measuring the tiny amount of energy released as heat when an individual bit is erased. See their article in Nature. Real computers today are said to operate within three orders of magnitude of the energy-efficiency limit which Landauer's bound imposes. So we can envision a new kind of impossible physical machine: one that can erase bits more coolly. The question is whether any complexity assertion has a side---true or false---that would enable a violation of this bound, thus `proving' the other side.

Physics and Math

The philosopher in us recoils dogmatically at the notion of such a ``physical proof.'' Complexity theory is part of mathematics, and mathematical assertions are not supposed to be ``contingent.'' This is a fancy philosophical term for propositions that are ``true in some possible worlds and false in others.'' In particular, the truth of a mathematical proposition is not supposed to depend on any empirical fact about our particular world.

Of course physical observations can sometimes aid in discovering proofs. They can help one guess which side---true or false---to try to prove. What we mean is something stronger: whether appeals to physical observations or laws can constitute a proof by themselves---or part of a proof, or some kind of certificate of a proof.

Our openness begins by coupling something Landauer himself was noted for saying, Information is inevitably physical. with the following translation of what John Wheeler meant by ``it from bit'': Physics is ultimately informational. Information is what we ``do''---with theorems and proofs---and mathematical theorems underlie the most fundamental physical models. If information and physics are as tightly bound as they say, we ought to expect some ``flow'' in the other direction. The question remains, how?

We will not try here to evaluate particular papers we have seen or heard about, such as this or this by Alexandre de Castro of Brazil, or this on energy complexity by Feng Pan, Heng-liang Zhang, and Jie Qi of China. This paper by Y.N. Zayko of Russia reaches the opposite conclusion about $latex {\mathsf{P = NP}}&fg=000000$ from Landauer's work, so they can't all be right, while this by Armando Matos also treats Landauer's principle and factoring. We invite comments from better-versed readers. Rather, we wish to examine the larger issue: can physics be used to prove mathematical theorems? Indeed.

Physical Proofs?

Imagine that someone shows the following: If $latex {\mathsf{P=NP}}&fg=000000$, then some physical principle is violated. Most likely this would be in the form of a Gedankenexperiment, but nevertheless it would be quite interesting. Yet I am at a loss to say what it would mean. Indeed the question is: ``Is this a proof or not?''

Let's call an argument that shows that If some mathematical statement $latex {X}&fg=000000$ is true, then some physical principle $latex {Y}&fg=000000$ is incorrect a Physics Proof---say a PP for short. And let's call a usual math proof a MP. Can we prove something about the relationship between PP's and MP's? Can we, for example, prove statements in math via PP's? Even statements that we already know are correct? Can there exist a PP that shows that set theory is consistent? Does this violate the famous Incompleteness Theorem of Kurt Gödel?

We have discussed this in an earlier post, in which we also referenced papers by Scott Aaronson and Bennett himself. All this has left us still quite interested in the possibility that PP could exist, and we will try to give some new illustrations of the possibilities.

A Trivial Example

Let's look at a PP that shows that multiplication of natural numbers is commutative. Suppose that $latex {n}&fg=000000$ and $latex {m}&fg=000000$ are such numbers greater than zero. Consider the a box $latex {n=3}&fg=000000$ by $latex {m=4}&fg=000000$ of unit squares:

*	*	*	*
*	*	*	*
*	*	*	*

Then it's area is clearly $latex {nm}&fg=000000$. Now rotate the box:

*	*	*
*	*	*
*	*	*
*	*	*

The area is invariant under rotation---this is the physical principle that we are using. But now the area is $latex {mn}&fg=000000$. So we conclude that

$latex \displaystyle nm = mn. &fg=000000$

Wow, what a surprise---if we were doing standup comedy we would not expect much more than tomatoes from this. But an interesting post with this example by Peter Cameron goes on to show that the formal proofs in Peano arithmetic and set theory also have their downsides. Our understanding is this method is used in some grade schools as a way to help students understand multiplication.

Relationship to Relativity

We have previously told the history of the ``no-cloning'' theorem in quantum mechanics. A paper purporting to demonstrate faster-than-light (FTL) communication was found to rely on the assumption that an arbitrary pure binary quantum state can be duplicated by a quantum process. If one takes FTL communication to be a violation of physical law, this could be said to constitute a proof of the negation of the assumption. To be sure, a proof was soon found by several people using elementary linear algebra. Hence the no-cloning theorem itself is just a piece of mathematics. the question is whether it could have been said to be ``already proved'' by physics before the simple proof was found.

in quantum communication theory, it seems to be legitimate to argue a theorem based on its negation implying FTL communication. We keep intending to post in greater detail about a paper by Ulvi Yurtsever which we read as showing that if one could gain a nontrivial probabilistic prediction advantage against an unbiased quantum random source, then local causality would be violated---in particular, FTL communication would be possible. There are other potential examples on Philip Gibbs' FTL page, currently maintained by physicist John Baez at UC Riverside.

The Information Ratchet

Ken has thought about this recently upon reading some reviews of the book Life's Ratchet by Peter Hoffman of Wayne State University. According to a review in Nature:

engagingly tells the story of how science has begun to realize the potential for matter to spontaneously construct complex processes, such as those inherent to living systems.

Our question is,

Can we possibly judge the differential impact on the speed of this ratchet between the truth and the falsity of $latex {\mathsf{P = NP}}&fg=000000$, or of more-concrete algorithmic assertions?

If so, that is if we can quantify the impact, then by observing the speed of generative life processes in the lab, coupled with mapping out the early history of life on Earth, we might ascertain the (un)availability of certain concretely feasible approximative or exact algorithms empirically, in advance of possibly proving it.

Relationship To Time Travel

For an even more speculative notion, perhaps an unfair one, suppose that we want to factor a large number. Assume it would take $latex {1,000}&fg=000000$ years on a laptop. Here is what we could do: We create a computer that can run for a thousand years. This would no doubt require some clever engineering: the machine probably would need to do self-repair and also use a renewable source of power. While it would be a difficult piece of engineering, it does not seem to violate any physical principles. Start it running on the factoring problem. Then jump into your time machine, go into the future, get the answer, and return. This means we could do a huge computation in seconds. Does this mean that we can ``prove'' that If time-travel is possible, then many concrete ``hard'' factoring instances are easy? I am very confused. I hope you are too, even before looking up literature on ``closed timelike curves'' and algorithms such as in section 8 of Scott's survey. Note, taking the contrapositive yields that if you believe that certain concrete instances of factoring are yea-hard, then time travel is impossible.

Open Problems

What do you think? If someone found a PP of $latex {\mathsf{P \neq NP}}&fg=000000$ would that prove they are not equal? Would this win the Clay Prize? What would it really mean?

We note that Landauer's principle did inspire theorems about reversible computation by Bennett and others; this and other stories are told in a lovely memoir by Bennett with Alan Fowler written in 2009 for the National Academy of Sciences.