# Packing boxes and proof of Riemann Hypothesis

There’s a finite (and not unimaginably-large) set of boxes, such that if we knew how to pack those boxes into the trunk of your car, then we’d also know a proof of the Riemann Hypothesis. Indeed, every formal proof of the Riemann Hypothesis with at most (say) a million symbols corresponds to some way of packing the boxes into your trunk, and vice versa. Furthermore, a list of the boxes and their dimensions can be feasibly written down.

His later commented to explain where he get this from: "3-dimensional bin-packing is NP-complete."

I don't see how these two are related.

Another question inspired by the same article is here.

-

 The "solutions correspond one-to-one" (and onto) is key, or else his statement doesn't hold. I find that very hard to believe - reductions from A to B are rarely such that every problem in A corresponds to exactly one problem in B. – BlueRaja - Danny Pflughoeft Jul 28 '10 at 22:57 Problems don't have to correspond, only solutions for a fixed instance of each problem. I believe we do have such a "parsimonious" reduction (they're quite common actually), but even if we don't, something similar in spirit still holds: if we can solve bin packing, then we can solve it a few times to obtain a proof of the Riemann hypothesis. (E.g. solve the bin packing instances corresponding to "does there exist a proof with first bit 0?" then repeat once you know the first bit, etc.) – ShreevatsaR Jul 28 '10 at 23:33 so we are assuming any proof can be verified in polynomial time? If that's true then it all makes sense. – Chao Xu Jul 29 '10 at 1:49 @Chao Xu: Yes, a "formal proof" (see Wikipedia or this Notices of the AMS issue) is a proof written in a certain precise form that can be checked by computer. Actually, if we fix a bound on the proof length at 1 million, we don't even need to say "polynomial time", since the size is a constant. :-) – ShreevatsaR Jul 29 '10 at 1:59 See also this answer by T... – ShreevatsaR Aug 3 '10 at 5:14