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
 A: One can devise "crystallization problems" that are NP-complete by using square tiles where edges need to match up (like in DNA origami). See also 5.3.4 in The Nature of Computation by Moore & Mertens for another proof.
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...
Hence, in the normal case where temperature declines faster than the formula above (i.e. nearly always) we should only expect "good" crystals if the naive attachment method of attaching at the currently most favorable site works, e.g. for tilings/crystals where only local information matters like in simple lattices. When the configuration space becomes more complex (like in crystallizing proteins, where 3D direction and shape starts to matter) this often does not work and would-be crystallizers tend to become frustrated.
So in the end the slowness of the empirically required annealing schedule likely measures the amount of long-range constraints in the tiling rules rather than a pure computational complexity, but the two tend to have a relationship.
