Hacker News new | ask | show | jobs
by adamgravitis 3551 days ago
The main computationally intractable problems around drug discovery surround protein folding and identifying macromolecule shapes. This is necessary to infer receptor sites for potential drug targets.

The problem is massively intractable. QC could revolutionize the space.

1 comments

Remember though, NP complete problems still are intractable (exponential complexity) even for quantum computers, to say nothing of NP hard.

Unger and Moult (1993) have shown a three-dimensional protein folding model to be NP-complete, and a two- and three-dimensional mathematical model describing the folding process as a free energy minimization problem is NP-hard:

https://www.gwern.net/docs/1993-fraenkel.pdf