3 ms·
Yes, this is true but only from the reference frame of the cosmic background radiation. It is still possible that you can get O(n^3) from the reference frame of
by AlanSE 4y ago
Yes, this is true but only from the reference frame of the cosmic background radiation. It is still possible that you can get O(n^3) from the reference frame of the aliens themselves, because time dilation makes travel fairly fast. You get into some spacetime philosophy about what metrics are worth evaluating O against in the first place.
- lisper 4y agoOK, but even O(n^3) is still polynomial, not exponential. That matters. There's a reason that P=?NP is a thing.