26. Dedekind Numbers, counting monotone Boolean functions on a finite set: formula's and complexity issues.
Invited abstract in session FB-1: Complexity, stream Complexity.
Friday, 10:30 - 12:00Room: L226
Authors (first author is the speaker)
| 1. | Patrick De Causmaecker
|
| Computer Science, CODeS research group, KU Leuven |
Abstract
In March 2023, we were one of groups to independently compute the ninth Dedekind Number, i.e. the number of monotone Boolean functions on the subsets of a set of nine elements.
Throughout the 20th century, actually since the statement of the problem in 1897 by Richard Dedekind, computing these numbers has served as a test case for both the growth of mathematical understanding of combinatorial problems and the growth of computational power. In this talk we present the methods used in 2023 in relation with earlier achievements, and how these were implemented on today's supercomputers. We enter into the complexity properties of the used formula's and we explain how the current status of computing hardware and software impacts the possibilities and power of the proposed approaches. Consequently we generalise on some of the methods and discuss recent developments. We speculate how this, together with upcoming technology, will take us to the computation of the tenth number.
Keywords
- Algorithm and Computational Design
- Graph theory and networks
Status: accepted
Back to the list of papers