4 ms·
Not really an answer to your question, but is the problem really NP-complete, or just combinatorially difficult? For example how is this condition of NP-complet
by ashtonbaker 5y ago
Not really an answer to your question, but is the problem really NP-complete, or just combinatorially difficult? For example how is this condition of NP-completeness satisfied?
> it is a problem for which the correctness of each solution can be verified quickly [0]
[0] https://en.wikipedia.org/wiki/NP-completeness https://en.wikipedia.org/wiki/NP-completeness
- Cas9 5y agoAccording to this answer[0] it seems it's actually NP-Hard, my bad. Haven't seen the proof though, and I'm not an expert. [0] https://cs.stackexchange.com/questions/128493/is-protein-folding-really-np-hard-and-how-to-show-that https://cs.stackexchange.com/questions/128493/is-protein-fol...