Real-world relevance is orthogonal to complexity.
Edit: We don’t know the best programs, but we can approximate the bounds with some confidence that, unless some paradigm-changing discovery is made, the programs to solve digit multiplication would be significantly simpler. (This is not a formal argument, but the intuition is very strong for most people who study the problems seriously.)
Kolmogorov complexity is a distinct quantity. How did you compute this quantity?
If you’re a purist, you write the programs in MIX and you count ops. Or whatever your preferred Turing Machine is.
I know that sounds pedantic and this is the internet and not a scientific paper etc, but if this is an informal discussion then formal terminology like "Kolmogorov complexity" has no place in it and the purpose of the OP would, I think, be better served by using an informal term. If you 're gonna use maths, use maths. If you 're gonna wave hands, then wave hands, by all means. But don't mix the two, it just makes a mess.
Because at the end of the day I can just say, "no, I don't believe that multiplication has smaller Kolmogorov complexity than Starcraft's pathfinding"... and then, what? Where do we go from there? The OP says "yes it does", I say "no it doesn't", the OP says "does too", I say "nuh-huh". And we just waste our time.
> yes, I can assure you the Kolmogorov complexity ...
This is a strong comparative statement, and it's clear that it's an assertion but not a proof. So it's perfectly fine for you to say "I don't believe that" and then you would give your reasoning. Of course the conversation didn't go that way because it's pretty obvious to everyone that this is actually true even though we don't have a proof. And it's extremely likely that if you could find a minimal multiplication algorithm and enumerate all the Turing machines up to that length you could prove that none of them solve the harder problem. This is where the intuition comes from.
> using an informal term
But the OPs argument wasn't that one program would happen to be longer, but rather that it must by necessity be longer, because the problem is fundamentally more complex, which is exactly what the formal concept was created to capture.
> Kolmogorov complexity is a formal concept that does not admit intuitive judgements
This is a bad way of thinking about maths. The value of formal concepts is precisely that they give us tools for making intuitive judgements more effectively and give us a wider variety of tools to manipulate and express our intuition. As intuitions become conjectures and theorems, we accumulate new bedrock we can use for new intuitions, but don't short-circuit your thinking by saying that intuition about technical terms is off-limits. That's literally what they are good for.
I don't agree. I don't need formal terms to develop intuition. Formal terms are necessary when speaking formally, and they are only detracting from the point of a discussion otherwise.
And I don't agree with this either:
>> But the OPs argument wasn't that one program would happen to be longer, but rather that it must by necessity be longer, because the problem is fundamentally more complex, which is exactly what the formal concept was created to capture.
The way I understand it the formal concept is useful in proofs of the impossibility to calculate various other quantitites. Its utility is not to argue that this or that program should intuitively have lower Kolmogorov complexity.
To be honest, I'm so confused by the use of the term by the OP that I have no idea what they meant to say with it.
OP was simply saying that, in any general-purpose programming language (where all possible programs are expressible and none are unfairly favored) the solution to problem B will inevitably be longer than problem A. This is quite a bit more precise than just saying "a more complicated problem", and if you have the intuition behind it, there's no reason not to use the term.
There are obvious disadvantages to the current machine approaches, but they nonetheless achieve very good results and beat the vast majority of players of those games.