Galactic Algorithms: Theoretical Computer Science Concepts with Impractical Performance
By
tmtvl
Crackling crust, pillowy middle. The kind of bagel that earns a second cup of coffee.
Summary
A galactic algorithm is a theoretical computer science concept referring to algorithms with record-breaking asymptotic performance that are never used in practice due to practical constraints. These algorithms only show performance gains for problem sizes so large they never occur in real-world scenarios, or their complexity outweighs any practical benefits. The term was coined by Richard Lipton and Ken Regan, who noted such algorithms would never be used on Earth-based data sets. Despite their impracticality, galactic algorithms can still contribute to computer science by advancing theoretical understanding and inspiring practical improvements.
Key quotes
· 4 pulledA galactic algorithm is an algorithm with record-breaking theoretical (asymptotic) performance, but which is not used due to practical constraints.
Typical reasons are that the performance gains only appear for problems that are so large they never occur, or the algorithm's complexity outweighs a relatively small gain in real-world performance.
Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.
Even if they are never used in practice, galactic algorithms may still contribute to computer science.
You might also wanna read
The History of Pipes, Forks, and Zombies in Unix Systems
This article discusses the history and concept of pipes in Unix systems, focusing on Doug McIlroy's original vision of coupling programs lik
Sally A. McKee, Computer Science Professor and Former Microsoft/DEC Engineer, Dies at 61
Obituary for Sally A. McKee, a 61-year-old renowned computer science professor who passed away on Feb. 12 in Greenville, S.C. after a short
online-tribute.com·1mo ago
Demystifying Floating Point Numbers: An Interactive Guide
An in-depth technical blog post that demystifies floating point numbers, explaining their internal representation and behavior. The author i
ciechanow.ski·1mo ago
Binary GCD Algorithm: A Faster Alternative to Standard Euclidean Algorithm
The article explains the binary GCD algorithm, a faster variant of the Euclidean algorithm for computing greatest common divisors. It covers
Demystifying Fifth Normal Form (5NF) in Relational Database Design
This article provides a critical examination of fifth normal form (5NF) in relational database design, arguing that traditional explanations
kb.databasedesignbook.com·1mo ago
Computer Science Pioneer Tony Hoare Passes Away at 92
The article announces the passing of Tony Hoare, a pioneering computer scientist and Turing Award winner, at age 92. It reflects on his majo
blog.computationalcomplexity.org·2mo ago