Talk:Galactic algorithm: Difference between revisions

Revision as of 16:50, 4 September 2022

Latest revision as of 14:51, 30 June 2025

(9 intermediate revisions by 6 users not shown)

Line 1:

{{WikiProject banner shell|class=C|1=

{{WikiProject Mathematics |priority=Low}}

}}

== Multiplication algorithm ==

Line 15 ⟶ 19:

This makes no sense and isn't cited. Is it correct? Galactic algorithm are impractically because they involve data that isn't in practice used? Increased 'Computer sizes' won't change that. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/61.68.214.83|61.68.214.83]] ([[User talk:61.68.214.83#top|talk]]) 11:02, 5 October 2019 (UTC)</small> <!--Autosigned by SineBot-->

:Data sizes also catch up too. For example, the [[AKS test]] at some point must begin outperforming all other known deterministic primality tests, and it's possible that future computer sizes will realize that. The [[Strassen algorithm]] would not have been practical on early computers (today's data matrices are far larger than anything back then). Even with quantum computers, [[Shor's algorithm]] is arguably galactic at this time as it is impractical for all but the smallest integers at this time, even though we believe we can construct quantum computers of sufficient size to make it more practical than classical algorithms.--[[User:Jasper Deng|Jasper Deng]] [[User talk:Jasper Deng|(talk)]] 11:10, 5 October 2019 (UTC)

:> Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical.

:The practical example of [[stealth aircraft]] should be mentioned in the article. A complete theory of radar reflection minimalization was first created by a *soviet* mathematician in 1964 and published in open scientific press, because the resulting equations were considered transcomputable for the foreseeable future. The CIA archived that thesis and checked back on it regularly. By the late 1970s, [[Moore's Law]] increased free-world computing power enough that stealth airframe shapes composed of just flat panels could be designed and thus the [[F-117]] was born. By the late 1980s, further increases in CPU / RAM power allowed simulating the radar reflection of elaborate 3D-curved surfaces and the Northrop [[B-2 Spirit]] strategic stealth bomber was produced (albeit at the insane price tag of 2 billion then-dollars apiece.) It's similar but smaller and supposedly more affordable cousin, the [[B-21 Raider]] has just been unveiled, with her first flight expected in early 2023. [[Special:Contributions/92.249.156.122|92.249.156.122]] ([[User talk:92.249.156.122|talk]]) 17:29, 17 December 2022 (UTC)

::Pyotr Yakovlevich Ufimtsev is the name of the soviet scientist mentioned above. [[Special:Contributions/92.249.156.122|92.249.156.122]] ([[User talk:92.249.156.122|talk]]) 17:33, 17 December 2022 (UTC)

== Shannon is not an example ==

Shannon's coding example is not related to the scale of the input and therefore it is not a galactic algorithm. [[User:Fulldecent|Full Decent]] ([[User talk:Fulldecent|talk]]) 17:18, 5 October 2019 (UTC)

:Agreed - a "galactic algorithm" should be impractical on human-sized problems: as the name implies - it's only worthwhile on "galactically-sized" problems.

:In the Shannon coding example, this algorithm takes <math>O(2^n)</math>, which gets increasingly impractical as n gets galactic. In fact, at small n (e.g. n=1), this algorithm is quite reasonable.

:There ''is'' likely a way to describe this problem as galactic in terms of the length of the message rather than n, and making n part of the constant (much as the paragraph on subgraphs does). But this paragraph on Shannon doesn't do that. [[User:AMWJ|AMWJ]] ([[User talk:AMWJ|talk]]) 14:51, 30 June 2025 (UTC)

== AKS primality test? ==

Line 29 ⟶ 40:

The example given of simulated annealing with a logarithmic cooling schedule does not seem to fit the definition of a galactic algorithm as being asymptotically better than practical solutions, unless I am misunderstanding?

[[Special:Contributions/2A00:23C6:4C28:9E01:E9CC:320E:F1BE:BFA4|2A00:23C6:4C28:9E01:E9CC:320E:F1BE:BFA4]] ([[User talk:2A00:23C6:4C28:9E01:E9CC:320E:F1BE:BFA4|talk]]) 16:50, 4 September 2022 (UTC)

:To my knowledge, the asymptotic superiority comes from being able to find the minimum of *any* objective function, no matter how ill-formed. No practical optimization algorithm can make this promise. [[User:LouScheffer|LouScheffer]] ([[User talk:LouScheffer|talk]]) 20:29, 4 September 2022 (UTC)

== Two kinds of galactic-ness? ==

This article mixes up two closely related kinds of galactic. In both cases, the algorithm is better than any used in practice.

*In one case (like multiplication), it only excels on impractically large examples.

*In other cases (Shannon, Simulated annealing) it gives superior results, but only if impractical amounts of computer power are used.

The second kind was not included in the original definition, but my opinion is that it is in the same spirit - it's a theoretically great algorithm that is not practical. And it has the same benefits as the first kind (inspiring research, showing limits, etc.)

Perhaps a better title might be "Superior but impractical algorithms", but I think "Galactic" is a catchier shorthand for this. [[User:LouScheffer|LouScheffer]] ([[User talk:LouScheffer|talk]]) 20:26, 4 September 2022 (UTC)

== Original research ==

While the concept is understandable, but it seems that this neologism didnt catch up. Therefore the whole article is [[WP:SYNTH]], because refs cired for the examples do not use the term. - [[user:Altenmann|Altenmann]] [[user talk:Altenmann|>talk]] 02:30, 24 November 2023 (UTC)

:While good faith, I think this viewpoint is incorrect. It is true that many of the algorithms cited do not call themselves by the specific word "galactic", but they include phrases indicating they are not likely to be used in practice, or else critics have noted this for them. In terms of detailed changes, the two sentences marked with "citation needed" are given directly in the first reference, as was the removed section on a hypothetical n^2^100 algorithm for SAT. Since this article is already cited in both the lede and the paragraph, citing each individual sentence seems excessive, though they could be included if editors feel strongly they are needed. As far as the removed section on the travelling salesman problem, this qualifies for the references article's definition, which is "simpler algorithms are used in practice". I've changed the lede to include this additional (cited) definition. [[User:LouScheffer|LouScheffer]] ([[User talk:LouScheffer|talk]]) 12:39, 25 November 2023 (UTC)