The Traveling Salesman section has a fun example: a new algorithm improved the results by 10⁻³⁴ percent!
This was mentioned in https://lobste.rs/s/uxhkqd/weird_ways_multiply_really_fast_with
I remember a course from a Ph. D Student of Alain Colmerauer the creator of Prolog.
She added a new method to solve a new class of problems with Prolog. She explained her work for a whole month to us until the last day when she concluded by the complexity of her algorithm which was a tower of 2 from the size of the problem.
So you could only use her method to solve this class of problems up to size 5.
Does the concept of a Galactic Algorithm imply the existence of Galactic Bugs?
Sort of reminds me of that bug that existed in the Java libraries for 9 years…. only got discovered when ram and use cases got large enough to trigger it!