Re:Galactic algorithm
by hermitcrab on Sunday December 03, 2023 @05:29AM
(#38506086)
I was trying to keep things simple, by talking about algorithms that have precise answers (such as multiplying 2 numbers or sorting a list). In that case you would expect the galactic and nongalactic algorithms to give the same answer, but with different time and space characteristics. Perhaps I should have been clearer.
Consider the TSP problem from TFA, in this case two approximation algorithms were presented, one marginally better, meaning the answer would be different.
I believe channel capacity encoding was like this as well, but that is not in my wheelhouse.