Galactic algorithm [completely decoded]

Galactic algorithm is an algorithm that achieves optimal performance or a theoretical improvement for a significantly large input that makes it unusable in practice. For many Galactic Algorithms, input is of size larger than the size of our Universe or size we cannot store in practice.
Example of Galactic Algorithms are:

  • Integer Multiplication by Harvey
  • Traveling Salesman Problem by Karlin
  • Boolean satisfiability problem (Polynomial)

In general, asymptotic behavior of Galactic Algorithms are better than the counter-part algorithms that are used in practice for the given problem.

Why are Galactic Algorithms unusable?

Galactic Algorithms are unusable because of the hidden constant factors in its time complexity or asymptotic analysis. The constant factors are so large that simple algorithms perform better for small data size or the data size that is used in practice.

If sufficiently large input data is used, then the performance improvement of Galactic Algorithms are observed. Moreover, Galactic Algorithms are hard to implement in practice as well.

Hence, Galactic Algorithms are unusable because:

  • Huge hidden constant factors that cancel out only for extremely large input
  • Other algorithms perform better for input of standard size
  • Hard to implement in practice

Origin

The term "Galactic Algorithm" was coined by Richard Lipton and Ken Regan in 2010.

"Galactic Algorithm" become popular in 2020 following the development of the first O(N logN) time Integer Multiplication algorithm (by Harvey). This solved the 60 year old problem if O(N logN) algorithm exists?

The only downside of the algorithm is that it cannot be used in practice as other algorithms will outperform it for the current problem sizes.

Example of Galactic Algorithms

Example of Galactic Algorithms are:

  • Integer Multiplication by Harvey
  • Traveling Salesman Problem by Karlin
  • Boolean satisfiability problem (Polynomial)

Integer Multiplication by Harvey

The most optimal algorithm for Integer Multiplication of two numbers N takes O(logN loglogN) but is a Galactic Algorithm and cannot be used in practice.

It was developed by David Harvey in April 2019 and is based on 1729 dimensional Fourier space. This means the algorithm reaches its theoretical goal when the input numbers have at least 2^(1729^12) bits (that is 10^(10^38) digits). This is larger than the number of atoms in our Universe and hence, such large numbers cannot be stored in practice.

Why 1729?

1729 is a very special number and appears at several places. It is known as the Ramanujan Hardy Number. For this specific Multiplication algorithm, the author mentions:

In Section 5 we establish (1.3) with the explicit constant K= 1728, and in Section 5.4 we list some optimisations that improve it to K= 8.
In Section 5, we will simply take d:= 1729 (any constant larger than K would do)

Hence, we get 1729 in this Galactic Algorithm.

Traveling Salesman Problem by Karlin

The best algorithm for Traveling Salesman Problem is Christofides algorithm. It finds a path that is atmost 50% longer than the actual optimal path. There are other algorithms that can find better paths but there is no garantee of success in the algorithms.

The improvement over this was achieved by a Galactic Algorithm proposed by Anna R. Karlin, Nathan Klein and Shayan Oveis Gharan in September 1, 2020. It improved over the previous result by 10^-34 %. In fact, this algorithm finds a path that is 1.5-e times longer (where e <= 10^-36) than the most optimal path.

Boolean satisfiability problem

The theoretical most efficient algorithm for Boolean satisfiability problem has a time complexity of O(N ^ (2^100)). This is a polynomial algorithm in contrast to other exponential algorithms.

Though the polynomial algorithm is not practical to be used, it has significant theoretical implications:

  • It relies on assuming that P=NP. If the algorithm is correct, then it indirectly solves one of the most difficult theoretical problems in Computer Science that is P=NP?.
  • It is the fastest algorithm for this problem theoretically.
  • Due to the most O(N ^ (2^100)), exponential algorithm will perform better for small numbers N and the polynomial algorithm will lead only for large numbers N which are not practically.

O(N ^ (2^100)) ~ O(N^(10^30))
O(2^N)

Hence, if we assume N = 10^1000, then:
O(N ^ (2^100)) ~ O(N^(10^30)) ~ O(10^(1000 * 10^30)) ~ O(10^(10^33))
O(2^N) ~ O(10^103)

Hence, even for N=10^1000, the exponential algorithm is much smaller than the Polynomial Algorithm. Hence, this is a Galactic Algorithm.

Matrix Multiplication

The fastest known Matrix Multiplication algorithm is:
Coppersmith Winograd algorithm with modifications by Andrew Stothers and Virginia Vassilevska William.

The catch is that the algorithm is a Galactic Algorithm and will not bring in any significant performance improvement for numbers used in practice.

Note that Coppersmith Winograd algorithm is used in practice. It is the modified version by Andrew Stothers and Virginia Vassilevska William which is a Galactic Algorithm.

Conclusion

With this article at OpenGenus, you must have the complete idea of Galactic Algorithm.

If you intend to do intensive research in Algorithms and Computer Science, Galactic Algorithm is a very important topic.

If you are a Software Developer and focus only on topics that will help you build better systems, then Galactic Algorithms may not be of use for you.

Either way, you should know that such algorithms like Galactic Algorithms exist and this takes Computer Science to the very edge of Computing Power spread across the Universe.

References