New answers tagged kolmogorov-complexity
0
I've seen this concept explained as Solomonoff induction, a formalization of Occam's razor.
Given some set of Turing machines that fit the data, the one with the lowest complexity is likely to be the one that truly models it.
16
You can say that an algorithm is asymptotically optimal in such a case.
In general, people might also say that an algorithm is optimal in some other sense, like assuming some particular complexity-theoretic conjecture like (S)ETH.
Top 50 recent answers are included
