michael_nielsen

I wonder if one can find empirical evidence of a link between the Kolmogorov complexity of a task and that of its solutions. Intuitively, I would think that problems that are simple to fully specify can be solved with comparably simple algorithms.

This logic appears specious. Many NP-Hard problems are simple to state.

Kolmogorov complexity doesn't care about time-to-solution, just length of minimal description. Logical depth incorporates time-to-solution.

If we don't care about the time to find a good solution, then maybe? For many problems there is a naive solution (brute force) that is trivial to describe and then there are better algorithms that are harder to describe. E.g. most combinatorial problems, matrix multiplication

1/ Fermat's last theorem is an counter example. Unless you are claiming that there is much simpler solution. Millennium problems are in