2
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ – Jon Custer Jul 14 '20 at 16:02
  • $\begingroup$ 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. $\endgroup$ – probably_someone Jul 14 '20 at 16:11
  • $\begingroup$ 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. $\endgroup$ – SagarM Jul 14 '20 at 16:30
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the absolutely amazing answer. And I do think theses processes are an effective local optimisation algorithms, but I think that global constrains are able to mess with their ease of finding a minima for example a layered water surface crystallises faster than a drop nature.com/articles/s41598-019-57169-1.pdf?origin=ppub . What do you think about this ? $\endgroup$ – SagarM Jul 15 '20 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.