NP-Vollständigkeit

Die Energieminimierung von Molekülen ist deshalb eine nicht-triviale Aufgabenstellung, weil die Anzahl lokal stabiler Strukturen - lokale Energieminima in der Ergebnishyperebene - exponentiell mit der Anzahl der im Molekül vorhandenen Atome zunimmt [16]. J.T. Ngo und J. Marks haben 1992 in [43] für ein erweitertes Faltungsmodell gezeigt, dass eine Energieminimierung von Proteinmakromolekülen ein NP-vollständiges Problem ist.