# Computational Complexity of Crystallisation?

If we look at crystallisation as a tiling problem, i.e. filling the space with a given set of tiles of arbitrary shape. Then the time that it takes to solve this problem has to be bounded below by the computational complexity of the tiling problem (of this kind) itself. Infact, maybe we can atribute amorphous ice formation while rapid cooling to the lack of time for solving the harder complexity problem. Has there been some work in this direction ?

I am obviously not expecting to make quantitative predictions from such an analysis, but it is interesting to note that if P != NP , then nature itself has to be bounded by computational limits. The question is inspired by Scott Aaronsons talk and what he says at 52:00 https://www.youtube.com/watch?v=8bLXHvH9s1A

• Well, atoms and molecules don't solve problems (complexity or otherwise). And, in typical crystallization kinetics, the 'complexity' to solve is quite limited - whether the piece fits in right here right now has little to do with pieces fitting in anywhere else. – Jon Custer Jul 14 '20 at 16:02
• The statement, "Nature itself has to be bounded by computational limits", necessarily assumes that nature is making computations using the same model of computation that we use to define complexity. As far as I know, there is nothing in nature that actually indicates that this is at all true. – probably_someone Jul 14 '20 at 16:11
• In my understanding, modern complexity theory is not about any algorithm solving a problem, infact it is indeed about inherent complexity of these problems. My point is to not see the process of crystallisation as computation, but is the fact that rate of crystallisation has to be bounded below by the complexity of solving this problem in general. – SagarM Jul 14 '20 at 16:30

However, when you try to run the actual crystallisation you will likely find that you get imperfect crystals rather than some magical solution to the NP-complete problem. In practice what happens is that tiles randomly attach where they fit, but also detach. The equilibrium in $$[\text{lattice}] + [\text{tile}] \rightleftharpoons [\text{lattice+tile}]$$ will be determined by the equilibrium constant $$K \propto \exp(-2\Delta G/k_B T)$$ where $$\Delta E$$ is the Gibbs energy difference between bound and unbound tile states. This means a certain degree of jumping around (more at higher temperatures) that will make tiles stay at more optimal places with higher probability. At low temperature they get stuck, but since interactions are local they may hence form patterns that prevent the larger "correct" pattern from forming. NP-complete cases have long-range constraints rather than just local ones.
Heating things first and lowering temperature slowly (simulated annealing or real annealing) allows convergence towards the global optimum (yay!) but to get there with probability 1 the temperature needs to decline as $$T(t)=\frac{c_1}{\log(t+c_2)}$$ (Geman & Geman 1984), which is sloooow...