Hallo, folks!

My name is Oliver, I'm interested in maths, computer science, and combinatorial problems.

I've been studying The Art of Computer Programming by Donald E. Knuth, working on some of the exercises and some of the open problems. In Volume 4A, chapter 7.1.2 the topic of boolean chains comes up. Basically, it's about a chain of boolean operations on some input values x_1, ..., x_n and intermediate results of those operations, such that a set of desired functions f_1, ..., f_m on those inputs can be evaluated. The goal is to make such a chain as small as possible, because that makes for small circuitry with fewer parts.

One example Knuth chose is the segments of a digital display, as we know it from (somewhat dated) alarm clocks or quartz watches. The inputs are the four bits of a number 0 to 15 (we want hexadecimal digits) and the seven output functions are whether each of the segments of the display should be turned on or off for that digit.



My goal is to find the minimal boolean chain for this problem, hoping to come up with some new algorithms or speed improvements to make this feasible; so that similar problems can be solved in the future. I've already found shorter boolean chains with an algorithm described on the website below, but to prove it is optimal I need to do an exhaustive search. I also suspect that there still are chains that are ONE step shorter than the one I found, based on the trajectory of smaller problems already solved, but for that I also need the exhaustive search.
Details of the project: https://orunge.org/boolean-chains/

I've already covered a large search space with my own machine and AWS Batch, but that approach will be too costly. That's where I hope BOINC Central can help!
Results can be tracked here: https://orunge.org/boolean-chains/#results-full

Please reach out if you are interested in more details.

Oliver

In reply to or's message of 29 Apr 2025:

Hallo, folks!

My name is Oliver, I'm interested in maths, computer science, and combinatorial problems.

I've been studying The Art of Computer Programming by Donald E. Knuth, working on some of the exercises and some of the open problems. In Volume 4A, chapter 7.1.2 the topic of boolean chains comes up. Basically, it's about a chain of boolean operations on some input values x_1, ..., x_n and intermediate results of those operations, such that a set of desired functions f_1, ..., f_m on those inputs can be evaluated. The goal is to make such a chain as small as possible, because that makes for small circuitry with fewer parts.

One example Knuth chose is the segments of a digital display, as we know it from (somewhat dated) alarm clocks or quartz watches. The inputs are the four bits of a number 0 to 15 (we want hexadecimal digits) and the seven output functions are whether each of the segments of the display should be turned on or off for that digit.



My goal is to find the minimal boolean chain for this problem, hoping to come up with some new algorithms or speed improvements to make this feasible; so that similar problems can be solved in the future. I've already found shorter boolean chains with an algorithm described on the website below, but to prove it is optimal I need to do an exhaustive search. I also suspect that there still are chains that are ONE step shorter than the one I found, based on the trajectory of smaller problems already solved, but for that I also need the exhaustive search.
Details of the project: https://orunge.org/boolean-chains/

I've already covered a large search space with my own machine and AWS Batch, but that approach will be too costly. That's where I hope BOINC Central can help!
Results can be tracked here: https://orunge.org/boolean-chains/#results-full

Please reach out if you are interested in more details.

Oliver

the wu in progress on the project concern chain boolean?

Yay! Great to see that we've completed at least 5% already.
I hope it's okay that I copied this information here: https://boincsynergy.ca/wiki/index.php/BOINC_Central

---