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!
The Traveling Salesman section has a fun example: a new algorithm improved the results by 10⁻³⁴ percent! https://en.wikipedia.org/wiki/Galactic_algorithm#Traveling_salesman_problem
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!
https://dev.to/matheusgomes062/a-bug-was-found-in-java-after-almost-9-years-of-hiding-2d4k