최소 부울 공식: 알고리즘 설계의 우아함과 과제

이 글은 5개 변수의 부울 함수를 표현하는 데 필요한 AND 또는 OR 연산자의 최소 개수를 계산하는 과정을 자세히 설명합니다. 처음에는 Floyd-Warshall 알고리즘의 변형을 사용했지만 비효율적인 것으로 판명되었습니다. 그 후 저자는 Alex Healy와 협력하여 함수의 대칭성 등의 특성을 활용하여 알고리즘을 크게 최적화하여 최종적으로 결과를 28로 계산했습니다. 이 글에서는 함수의 대칭성과 동치 클래스를 이용한 계산량 감소, 하향식 구성에서 상향식 검색으로의 전환 등 알고리즘 최적화 과정을 자세히 설명합니다. 최종 알고리즘을 통해 계산 시간은 추정 수개월에서 반나절 미만으로 단축되었습니다.