I think that this is a heuristic "near optimal" method rather than an exact analytic method (I have little to no idea of what that would be in protein folding).

I think that this is a heuristic "near optimal" method rather than an exact analytic method (I have little to no idea of what that would be in protein folding). A domain I do understand a bit which is np-hard is the travelling sales man. Computing an exact solution is unrealistic, but doing heuristic searches that get you to 99% of the optimal 99% of the time is relatively doable. But - you don't know that you are 1% from the solution... even if you are pretty confident that you are. It's quite possible (unlikely) that you are way off the optimal, but if you have a decent solution that's ok.