Galactic algorithm: Difference between revisions

Revision as of 20:07, 27 May 2025

Latest revision as of 11:22, 29 July 2025

(12 intermediate revisions by 7 users not shown)

Line 4:

== Possible use cases ==

Even if they are never used in practice, galactic algorithms may still contribute to [[computer science]]:

* An algorithm, even if impractical, may show new techniques that may eventually be used to create practical algorithms. See, for example, communication channel capacity, below.

* Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical. See, for example, Lowlow-density parity-check codes, below.

* An impractical algorithm can still demonstrate that [[conjecture]]d bounds can be achieved, or that proposed bounds are wrong, and hence advance the theory of algorithms (see, for example, Reingold's algorithm for [[connectivity (graph theory)|connectivity]] in undirected graphs). As Lipton states:<ref name="seminal"/>{{quote |This alone could be important and often is a great reason for finding such algorithms. For example, if tomorrow there were a discovery that showed there is a factoring algorithm with a huge but provably polynomial time bound, that would change our beliefs about factoring. The algorithm might never be used, but would certainly shape the future research into factoring.}} Similarly, a hypothetical algorithm for the [[Boolean satisfiability problem]] with a large but polynomial time bound, such as <math>\Theta\bigl(n^{2^{100}}\bigr)</math>, although unusable in practice, would settle the [[P versus NP problem]], considered the most important open problem in computer science and one of the [[Millennium Prize Problems]].<ref>{{cite journal |author=Fortnow, L. |year=2009 |title=The status of the P versus NP problem |journal=Communications of the ACM |volume=52 |issue=9 |pages=78–86 |url=https://www.cs.cmu.edu/~15326-f23/CACM-Fortnow.pdf|doi=10.1145/1562164.1562186 |s2cid=5969255 }}</ref><ref>{{cite journal |author=Fortnow, L.|first=Lance |year=20212022 |title=Fifty Years of P Versus NP and the Possibility of the Impossible |url=https://dl.acm.org/doi/pdf/10.1145/3460351 |journal=ProceedingsCommunications of the ACM Conference|volume=65 (Conference'17)|issue=1 |urlpages=https://lance76–85 |doi=10.fortnow.com1145/papers/files/pvnp50.pdf3460351 }}</ref>

== Examples ==

Line 40:

=== Hutter search ===

A single algorithm, "Hutter search", can solve any well-defined problem in an asymptotically optimal time, barring some caveats{{Such as|date=June 2025}}. It works by searching through all possible algorithms (by runtime), while simultaneously searching through all possible [[formal proof|proofs]] (by length of proof), looking for a proof of correctness for each algorithm. Since the proof of correctness is of finite size, it "only" adds a constant and does not affect the asymptotic runtime. However, this constant is so big that the algorithm is entirely impractical.<ref>{{cite arXiv|last=Hutter|first=Marcus|date=2002-06-14|title=The Fastest and Shortest Algorithm for All Well-Defined Problems|eprint=cs/0206022}}</ref><ref>{{Cite journal|last=Gagliolo|first=Matteo|date=2007-11-20|title=Universal search|journal=Scholarpedia|language=en|volume=2|issue=11|pages=2575|doi=10.4249/scholarpedia.2575|issn=1941-6016|bibcode=2007SchpJ...2.2575G|doi-access=free}}</ref> For example, if the shortest proof of correctness of a given algorithm is 1000 bits long, the search will examine at least 2⁹⁹⁹ other potential proofs first.

Hutter search is related to [[Solomonoff's theory of inductive inference|Solomonoff induction]], which is a formalization of [[Bayesian inference]]. All [[computable]] theories (as implemented by programs) which perfectly describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories. Again, the search over all possible explanations makes this procedure galactic.

Line 68:

}}</ref> But it remains purely theoretical: "Despite the new hash table’s unprecedented efficiency, no one is likely to try building it anytime soon. It’s just too complicated to construct."<ref name="OptimalBalance">{{cite web | last=Nadis | first=Steve | title=Scientists Find Optimal Balance of Data Storage and Time | website=Quanta Magazine | date=8 February 2024 | url=https://www.quantamagazine.org/scientists-find-optimal-balance-of-data-storage-and-time-20240208/ | access-date=12 February 2025}}</ref> and "in practice, constants really matter. In the real world, a factor of 10 is a game ender.”<ref name="OptimalBalance"/>

=== Connectivity in undirected graphs ===

Connectivity in undirected graphs (also known as USTCON, for Unconnected Source-Target CONnectivity) is the problem of deciding if a path exists between two nodes in an undirected graph, or in other words, if they are in the same [[Component (graph theory)|connected component]]. When Ifthe youusage are allowed to useof <math>O(\text{N})</math> space is allowed, polynomial time solutions such as [[Dijkstra's algorithm]] have been known and used for decades. But for many years it was unknown if this could be done deterministically in <math>O(\text{log N})</math> space (class '''[[L (complexity)|L]]'''), though it was known to be possible with randomized algorithms (class '''NLRL''').

InA breakthrough 2004, a breakthrough paper by [[Omer Reingold]] showed that USTCON is in fact in '''[[L (complexity)|L]]'''.,<ref>{{citation

| last = Reingold | first = Omer | author-link = Omer Reingold

| doi = 10.1145/1391289.1391291

Line 78 ⟶ 79:

| title = Undirected connectivity in log-space

| volume = 55

However, | despiteyear the= 2008}}.</ref> providing an algorithm with asymptotically better space requirement. However, [[SL (complexity)#ImportantOmer resultsReingold, 2004|thisthe algorithm's isvery galactic]]. Thebig constant]] hidden by the <math>O(\text{log N})</math> is so bigmeans that inon any practicalrealistic caseproblem it usesconsumes farsignificantly more memory and computation time than the well known <math>O(\text{N})</math> algorithms,. plusDespite itnot isbeing exceedinglyused slow.in practice, Sothe despitepaper beingis still a landmark in theory, and has been cited (more than 1000 citationstimes as of 2025) it is never used in practice.

| year = 2008}}.</ref>

However, despite the asymptotically better space requirement, [[SL (complexity)#Important results|this algorithm is galactic]]. The constant hidden by the <math>O(\text{log N})</math> is so big that in any practical case it uses far more memory than the well known <math>O(\text{N})</math> algorithms, plus it is exceedingly slow. So despite being a landmark in theory (more than 1000 citations as of 2025) it is never used in practice.

=== Low-density parity-check codes ===

'''[[Low-density parity-check code]]s''', also known as '''LDPC''' or '''Gallager''' codes, are an example of an algorithm that was galactic when first developed, but became practical as computation improved. They were originally conceived by [[Robert G. Gallager]] in his doctoral dissertation<ref>{{cite thesis |last=Gallager |first=Robert G. |date= 1960 |title=Low density parity check codes |url=https://dspace.mit.edu/bitstream/handle/1721.1/11804/32786367-MIT.pdf |degree=Ph.D |publisher=Massachusetts Institute of Technology }}</ref> at the [[Massachusetts Institute of Technology]] in 1960.<ref>{{Cite news |last=Hardesty |first=L. |date=January 21, 2010 |title=Explained: Gallager codes |url=http://web.mit.edu/newsoffice/2010/gallager-codes-0121.html |access-date=August 7, 2013 |journal=MIT News}}</ref><ref name="G1962">{{cite journal |last=Gallager |first=R.G. |date=January 1962 |title=Low density parity check codes |journal=IRE Trans. Inf. Theory |volume=8 |issue=1 |pages=21–28 |doi=10.1109/TIT.1962.1057683 |s2cid=260490814 |hdl=1721.1/11804/32786367-MIT}}</ref> Although their performance was much better than other codes of that time, reaching the [[Gilbert–Varshamov bound for linear codes]], the codes were largely ignored as their iterative decoding algorithm was prohibitively computationally expensive for the hardware available.<ref>{{cite journal |title=The development of turbo and LDPC codes for deep-space applications |last1=Andrews |first1=Kenneth S |last2=Divsalar |first2=Dariush |last3=Dolinar |first3=Sam |last4=Hamkins |first4=Jon |last5=Jones |first5=Christopher R |last6=Pollara |first6=Fabrizio |journal=Proceedings of the IEEE |volume=95 |number=11 |pages=2142–2156 |year=2007 |publisher=IEEE |doi=10.1109/JPROC.2007.905132 |url=http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf |archive-date=2009-06-20 |access-date=2025-03-04 |archive-url=https://web.archive.org/web/20090620174506/http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf |url-status=bot: unknown }}</ref>

|title=The development of turbo and LDPC codes for deep-space applications

|last1=Andrews |first1= Kenneth S |last2=Divsalar |first2= Dariush |last3=Dolinar |first3= Sam

|last4=Hamkins |first4= Jon |last5=Jones |first5=Christopher R |last6=Pollara |first6=Fabrizio

|journal=Proceedings of the IEEE

|volume=95

|number=11

|pages=2142–2156

|year=2007

|publisher=IEEE

|doi=10.1109/JPROC.2007.905132 |url=https://web.archive.org/web/20090620174506id_/http://coding.jpl.nasa.gov/~hamkins/publications/journals/2007_11_turbo_LDPC.pdf}}</ref>

Renewed interest in LDPC codes emerged following the invention of the closely- related [[turbo code]]s (1993), whose similarly iterative decoding algorithm outperformed other codes used at that time. LDPC codes were subsequently rediscovered in 1996.,<ref name="MacKay96">{{cite journal

|title=Near Shannon limit performance of low density parity check codes

|last1=MacKay |first1=David JC |author1-link=David J. C. MacKay|last2=Neal |first2=Radford M |author2-link=Radford M. Neal

Line 104 ⟶ 93:

|year=1996

|publisher=IET

|doi=10.1049/el:19961141 |bibcode=1996ElL....32.1645M |url=https://docs.switzernet.com/people/emin-gabrielyan/060708-thesis-ref/papers/MacKay96.pdf}}</ref> and Theybecame arepopular as a patent-free alternative.<ref name="Closing">{{cite journal |author=Erico Guizzo |date=Mar 1, 2004 |title=CLOSING IN ON THE PERFECT CODE |url=https://spectrum.ieee.org/closing-in-on-the-perfect-code |url-status=dead |journal=IEEE Spectrum |archive-url=https://web.archive.org/web/20210902170851/https://spectrum.ieee.org/closing-in-on-the-perfect-code |archive-date=September 2, 2021}} "Another advantage, perhaps the biggest of all, is that the LDPC patents have expired, so companies can use them without having to pay for intellectual-property rights."</ref> Even though the turbo code patents have now expired, LDPC codes also have some technical advantages, and are used in many applications today.

== References ==