الصيغ البولية الصغرى: أناقة وتحديات في تصميم الخوارزميات

تروي هذه المقالة رحلة حساب الحد الأدنى لعدد مُشغلي AND أو OR اللازمين للتعبير عن أي دالة بولية ذات خمسة متغيرات. في البداية، تم استخدام شكل مُعدل من خوارزمية Floyd-Warshall، لكنها ثبت أنها غير فعالة. تعاون الكاتب و Alex Healy لاحقًا، مستفيدين من تماثلات الدوال وخصائص أخرى لتحسين الخوارزمية بشكل كبير، ليصلوا في النهاية إلى النتيجة 28. تُفصّل المقالة عملية تحسين الخوارزمية، بما في ذلك تقليل الحساب من خلال تماثلات الدوال وفئات التكافؤ، والانتقال من بناء تصاعدي إلى بحث تنازلي. أدت الخوارزمية النهائية إلى تقليل وقت الحساب من أشهر مُقدرة إلى أقل من نصف يوم.