Galactic algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A 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.

A 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. The problem of deciding whether a graph G contains H as a minor is NP-complete in general, but where H is fixed, it can be solved in polynomial time.

The running time for testing whether H is a minor of G in this case is O(n^2) , where n is the number of vertices in G and the big O notation hides a constant that depends superexponentially on H . The constant is greater than 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) in Knuth's up-arrow notation, where h is the number of vertices in H . Even the case of h = 4 cannot be reasonably computed as the constant is greater than 2 pentated by 4, or 2 tetrated by 65536, that is, 2 \uparrow \uparrow \uparrow 4 = {}^{65536}2 = \underbrace{2^{2^{\cdot^{\cdot^2}}}}_{65536} .

Polygon triangulation

Polygon triangulation is the division of a polygon into non-overlapping triangles. Bernard Chazelle showed in 1991 that any simple polygon can be triangulated in linear time. However the proposed algorithm is extremely complex, and much simpler algorithms with near-linear O(\text{Nlog}^*\text{N}) performance are available, so these are used instead.

"His [Chazelle's] work represents an important theoretical breakthrough. However, his O(n) algorithm has appeared as very difficult to program and thus, to the knowledge of the authors, there is still no practical implementation available."

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376339587 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

17 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.