4 ms·
Isn't protein folding NP-hard? How are they getting around that problem?
by Sniffnoy 9y ago
Isn't protein folding NP-hard? How are they getting around that problem?
- adrianN 9y agoSomething being NP-hard doesn't preclude algorithms that solve or sufficiently approximate solutions for instances that occur in practice. SAT is also NP-hard, but you can download solvers that can handle most huge instances you need solved just fine.
- Sniffnoy 9y agoWhich is the sort of thing the article ought to talk about!
- russdill 9y agohttps://link.springer.com/chapter/10.1007/3-540-45154-4_10 https://link.springer.com/chapter/10.1007/3-540-45154-4_10 Monte-Carlo Sampling for NP-Hard Maximization Problems in the Framework of Weighted Parsing
- Sniffnoy 9y agoThe question isn't "How can you do possibly well on NP-hard problems?" It's, what particular tricks are these people using that allow them to get around the NP-hardness of this particular problem? The article doesn't talk about that and it should.