9
$\begingroup$

From Scott Aaronson's blog:

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.

1 Answers 1

9

The question of whether a formal proof of the Riemann Hypothesis exists (with at most a million symbols) is a problem in NP: given such a proof, it can be verified to be correct in polynomial time.

Bin-packing is NP-complete: this means that every problem in NP can be reduced to bin packing. In particular, the problem mentioned in the previous paragraph can. (This is a reduction that can be made explicit, so once we specify the proof verifier etc., we can carry out the steps of the reduction to get an instance of bin packing. We also need the reduction to be "parsimonious" i.e. solutions correspond one-to-one; I believe it is.)

  • 0
    See also [this answer](http://math.stackexchange.com/questions/944/proving-the-riemann-hypothesis-without-revealing-anything-other-than-you-proved-i/1441#1441) by `T..`.2010-08-03