Minimale Boolesche Formeln: Eleganz und Herausforderungen im Algorithmusdesign
Dieser Artikel beschreibt den Weg zur Berechnung der minimalen Anzahl an UND- oder ODER-Operatoren, die benötigt werden, um eine beliebige Boolesche Funktion mit fünf Variablen auszudrücken. Anfangs wurde eine Variante des Floyd-Warshall-Algorithmus verwendet, die sich jedoch als ineffizient erwies. Der Autor und Alex Healy kollaborierten später und nutzten die Symmetrien von Funktionen und andere Eigenschaften, um den Algorithmus deutlich zu optimieren und schließlich das Ergebnis 28 zu berechnen. Der Artikel beschreibt detailliert den Optimierungsprozess des Algorithmus, einschließlich der Reduzierung der Berechnungen durch Symmetrien von Funktionen und Äquivalenzklassen sowie des Übergangs von einer Bottom-up-Konstruktion zu einer Top-down-Suche. Der endgültige Algorithmus reduzierte die Berechnungszeit von geschätzten Monaten auf weniger als einen halben Tag.