• 0 Posts
  • 4 Comments
Joined 2 years ago
cake
Cake day: June 22nd, 2024

help-circle

  • Regarding the overinflated claim examples: I think this a misunderstanding between complexity theory and “everyday notion” of fast. In Complexity Theory, one is usually, interested in the asymptotic behaviour, i.e., how does the “performance” (number of steps) of an algorithm scale with the size of its input. In particular, an algorithm that runs for 10³⁰⁰ · |x| steps on an input of size |x| scales in the same way (linearly) as does an algorithm that runs for |x| steps, despite being massively slower. So the notion of “fast” or “efficient” that is sometimes used in complexity theory is not the same as one might expect if not familiar with the field.

    For example, concerning the exponential time hypothesis (ETH your second link), OpenAI did in fact find an algorithm that scales subexponentially (instead of exponential), thereby disproving the hypothesis, which was very unexpected to say the least. Of course, the algorithm (as noted in that post) is not practical, but that was never the goal (here the AKS primality test comes to mind, which checks whether its input is a prime, showing that primality checking can be done scaling polynomial in the input size).

    Actually, the ETH hypothesis has been considered as a way to tackle the P = NP millenium problem as ETH directly implies that P ≠ NP. Again, for these problems the question only lies in how an algorithm solving them scales with the input (i.e. asymptotic complexity) and not if the algorithms are practical. But people tend to describe/explain P as “problems which permit fast algorithms” conflating the complexity theory notion of fast with its everyday counterpart.

    tl;dr: There are different notions of “fast”. From a theoretical point of view, these algorithms are not practical. But that was never the goal as the problems are not concerned with practical algorithms but rather with an abstract notion of “fast”