NP-Probleme sind nicht hoffnungslos: Wie wir sie in der Praxis lösen
NP-Overrated
Viele lernen an der Uni: NP-harte Probleme sind praktisch unlösbar. Doch in der Praxis sind sie oft gar nicht so schlimm. Dieser Artikel zeigt, dass Dependency-Resolution, Type Checking, Scheduling und sogar SAT- und SMT-Probleme mit guten Algorithmen und Tools wie Gurobi oder SCIP in vernünftiger Zeit gelöst werden können. Ein Beispiel: Amazon löst täglich eine Milliarde SMT-Anfragen. Die Theorie ist nicht falsch, aber für die Praxis oft irrelevant – mit besseren Algorithmen und Timeouts kommt man weit.
In der Theorie gibt es keinen Unterschied zwischen Theorie und Praxis. In der Praxis schon. – Benjamin Brewster