For what I know of complexity measures in CS, they are aimed at rather large problems. With today's computing power, most people don't care about comparing the complexity of simple problems as they would all be solved in about the same time.
Yet, I turn out to be interested in some cost measures for small problems. For instance, although both
12 + 14 and
123503 + 589034 can be solved in the blink of an eye by today's computers, there seems to be a sense in which
123503 + 589034 is still more "costly" than
12 + 14.
So my question is : do you know of any such cost measures that would be appropriate for such small size problems?
Note 1 : I am interested in rather general answer for all kinds of problems, the addition one being just an example.
Note 2 : the best I have found so far is Kolmogorov's complexity, but for what I understand of it, it seems awfully hard to operationalize. First it appears to be dependent on the reference language, and second, once a language is chosen, it seems really hard to prove that a description of a string is of minimal length.
- Do you know of any measure which would be easier to implement?
- Am I missing something about Kolmogorov's complexity and is it easier to implement than I suggest?