4 ms·

So it's another galactic algorithm? https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm

poincaredisk 2y ago
I imagine the point of this algorithm, like a lot of algorithm research, is to prove the upper bound of complexity for this problem. Not to be used in practice (despite what this article seem to suggest). On a similar note, there's a lot of work put into optimal matrix multiplication algorithm. We know the lower bound is N*2, the obvious upper bound is N*3, the best (complexity wise, not practical at all) current algorithm is N*2.37, but we don't know how fast can it really get. Is it possible to write N*2 algorithm? We don't know.
- KolenCh 2y ago
  Both N^2 and N*2 are fine, but N*2 should really not mean what you want it to mean…
  - KolenCh 2y ago
    Now reading my comment again, I probably understand what happened. I typed N*2, and yet it showed as N*2. Probably this is why.
- FabHK 2y ago
  [flagged]
- nnoremap2 2y ago
  I mean nobody is stopping me from writing an exponential time algorithm.
  - Dylan16807 2y ago
    Sure? If you're slow on purpose that doesn't affect the upper bound set by the "obvious" method.
    - jakeinspace 2y ago
      I think they’re replying to the claimed upper bound of n^3. I’m not actually sure what that means.
      - Dylan16807 2y ago
        I'm not sure how to phrase this better than saying it's the bound set by the obvious method. Are you familiar with the obvious method of multiplying a matrix? It's n operations for each cell, and you have n^2 cells. Being worse on purpose is always possible, but it doesn't change that bound. It's the "obvious" upper bound, not the "how did you even get here without noticing the obvious method" upper bound.
      - demurgos 2y ago
        see schoolbook algorithm for the n^3 bound: https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication https://en.wikipedia.org/wiki/Computational_complexity_of_ma... It comes from directly applying the definition of matrix multiplication on a square matrix.
  - adrianN 2y ago
    Knowing an upper bound means you know that the best solution for the problem takes at most that much work. It does not mean that you can’t find worse solutions.
ddtaylor 2y ago
Thank you for introducing a term and concept I was not familiar with.
s_Hogg 2y ago
From that page: > Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical. Are there examples of Galactic Algorithms that now aren't Galactic Algorithms? edit: turns out some matmul algorithms are?
klysm 2y ago
I was about to ask if there was a term for this

poincaredisk 2y ago

I imagine the point of this algorithm, like a lot of algorithm research, is to prove the upper bound of complexity for this problem. Not to be used in practice (despite what this article seem to suggest). On a similar note, there's a lot of work put into optimal matrix multiplication algorithm. We know the lower bound is N*2, the obvious upper bound is N*3, the best (complexity wise, not practical at all) current algorithm is N*2.37, but we don't know how fast can it really get. Is it possible to write N*2 algorithm? We don't know.

KolenCh 2y ago
Both N^2 and N*2 are fine, but N*2 should really not mean what you want it to mean…
- KolenCh 2y ago
  Now reading my comment again, I probably understand what happened. I typed N*2, and yet it showed as N*2. Probably this is why.
FabHK 2y ago
[flagged]
nnoremap2 2y ago
I mean nobody is stopping me from writing an exponential time algorithm.
- Dylan16807 2y ago
  Sure? If you're slow on purpose that doesn't affect the upper bound set by the "obvious" method.
  - jakeinspace 2y ago
    I think they’re replying to the claimed upper bound of n^3. I’m not actually sure what that means.
    - Dylan16807 2y ago
      I'm not sure how to phrase this better than saying it's the bound set by the obvious method. Are you familiar with the obvious method of multiplying a matrix? It's n operations for each cell, and you have n^2 cells. Being worse on purpose is always possible, but it doesn't change that bound. It's the "obvious" upper bound, not the "how did you even get here without noticing the obvious method" upper bound.
    - demurgos 2y ago
      see schoolbook algorithm for the n^3 bound: https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication https://en.wikipedia.org/wiki/Computational_complexity_of_ma... It comes from directly applying the definition of matrix multiplication on a square matrix.
- adrianN 2y ago
  Knowing an upper bound means you know that the best solution for the problem takes at most that much work. It does not mean that you can’t find worse solutions.

ddtaylor 2y ago

Thank you for introducing a term and concept I was not familiar with.

s_Hogg 2y ago

From that page: > Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical. Are there examples of Galactic Algorithms that now aren't Galactic Algorithms? edit: turns out some matmul algorithms are?

klysm 2y ago

I was about to ask if there was a term for this