Content deleted Content added
LouScheffer (talk | contribs) →Multiplication algorithm: Original paper mentions reduction to 9 dimensions, but author states "additional refinements needed to make this practical". |
No edit summary |
||
Line 24:
The [[AKS primality test]] page claims it is a galactic algorithm. I had heard it had this property (though not the moniker ''galactic'' when the test was discovered). Any interest in adding this example to our main page, with citations? [[Special:Contributions/72.92.54.85|72.92.54.85]] ([[User talk:72.92.54.85|talk]]) 21:35, 3 May 2020 (UTC)
:AKS may or may not be galactic. AKS has a known running time of O(log(n)<sup>6</sup>). Competitor ECPP has an empirical run time of O(log(n)<sup>5</sup>), but no one knows the worst case for it. If the worst case is > O(log(n)<sup>6</sup>), the AKS is galactic, otherwise not. [[User:LouScheffer|LouScheffer]] ([[User talk:LouScheffer|talk]]) 17:56, 5 May 2020 (UTC)
== Optimality (simulated annealing) not an example of a galactic algorithm? ==
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)
| |||