I think this must have consequences for atoms, particularly metals. Particularly what happens under stress or shear. Maybe too for crystals and ordered regions of quasicrystals.
Interesting to think that the universe is solving NP-complete problems in real-time all day everyday. Mad respect.
Hmm, is that really the case tho? Here, can't you imagine that in a compressed sample of atoms, a small bounded region, things arrange themselves respecting minimum packings? I can. Why would you think that would be different to a global minima? It's the solution to the case, why would it be different?
It may be a global minimum but it doesn't have to be. If it ends up in a local minimum then going to a global one would reduce the total energy of the system but it may require additional energy first to 'go over the bump'.
I can't find a good source with packing but a very similar phenomenon is a soap film on a wire frame. Sometimes it gets stuck in a non-optimal configuration until you blow on it to give it a kick needed to reconfigure. You can see it at 19:35 in this talk by Matt Parker[1]
Sure, but I think if you're looking at atoms under compression or shear, there's a lot of energy to go around, so you're going to find them with plenty of energy enough to rearrange into the min energy configuration. And for small scales (define small, hah!) the local optima are going to be global optima because there's not "that many" other possible unoptimal configurations to end up in.
I'm not saying, you put a tungsten cube in the hydraulic press and instantly the cube atoms go into min packing config...but I am saying that in small enough (but not insignificantly small!) regions you're going to see these global optima packing solutions. And it's going to be everywhere all the time. You cut a wire with some pliars? I guarantee that some region in that wire the metal atoms were rearranged into an optimal packing under stress. That right there is nature solving an NP-complete problem. Happens all the time, I bet.
That the whole cube doesn't become optima is no biggie, but that these form at all is amazing to me. But also logical. It's just cool that nature solves NP complete problems as a matter of course. And we need "mathematicians to prove it". Nature does it without a care! :P ;) xx ;p
But also what about crystals? Can you just consider a perfectly formed crystal matrix, like a pure silicon wafer, to be the atoms in a global optima configuration? That may not correlate with packing exactly with packing as the unit is not always a cube, but you see what I mean? I don't think global optima in nature is such an irregularity or rarity as you may think. I'm not saying nature isn't messy, it is, but there's sufficient microstates and energy to get these global optimas all the time.
At least that's my intuition about it. I understand if yours differs, but that's no worries. Maybe this line of thought, that nature has ways to solve global optima easily all the time, can lead to better algorithms--different to simulated annealing.
Interesting to think that the universe is solving NP-complete problems in real-time all day everyday. Mad respect.