Answering "how will this protein most likely fold?" is computationally much easier (as far as we can tell) than answering "what protein will fold like this?"

Got a reference for that? It's not obvious to me (CS background, not bio).

What if you have an algorithm that attempts to solve the "how will this protein most likely fold?" problem, but is only tractable on 1% of possible inputs, and just gives up on the other 99%? As long as the 1% contains enough interesting structures, it'll still work as a subroutine for the "what protein will fold like this?" problem. The search algorithm just has to avoid the proteins that it doesn't know how to evaluate. That's how human engineers work, anyway: "what does this pile of spaghetti code do?" is uncomputable in the worst case, but that doesn't stop programmers from solving "write a program that does X".