Lexikon der Mathematik: Null-Eins-Programmierung
bezeichnet spezielle kombinatorische Optimierungsaufgaben.
Dabei werden für einen Teil der Variablen (oder alle Variablen) nur Belegungen aus der Menge {0, 1} erlaubt. Diese Einschränkung kann enormen Einfluß auf die Schwierigkeit einer algorithmischen Lösung haben. So ist beispielsweise die lineare Programmierung im Turingmodell in polynomialer Zeit lösbar, wogegen die gleiche Fragestellung für Lö-sungen in der Menge {0, 1} NP-vollständig (und damit vermutlich schwieriger) ist.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.