The physical universe doesn't need to "solve" protein folding in the sense of having a worst-case polynomial-time algorithm. It just needs to fold proteins. Many NP-complete problems are "mostly easy" with a few hard instances that rarely come up. (In fact, it's hard to find an NP-complete problem for which random instances are hard: if we could do this, we would use it for cryptography.) It's reasonable to suppose protein folding is like this.

Of course, if this is the case, maybe the AI doesn't care about the rare hard instances of protein folding, either.