NP-hard doesn’t say how hard it is to solve finite problems. Even for n = 1,000,000, O(e^n) isn’t necessarily problematic, if the constant is small enough, or if you throw enough hardware at it.

This “uses approximately 128 TPUv3 cores (roughly equivalent to ~100-200 GPUs) run over a few weeks”. That is a moderate amount of hardware for this kind of work, so it seems they have a more efficient algorithm.

Also, this algorithm doesn’t solve protein folding in the mathematical sense; it ‘just’ produces good approximations.