François CholletVerified account

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.

Such a link would be especially interesting with regard to the development of "general" AI

There are many problems that are easy to state but provably impossible to solve such as the halting problem and satisfiability of first order logic. How would that affect your hypothesis?

We're talking about solvable tasks, and concerned not about runtime complexity but instead about Kolmogorov complexity of the shortest possible solution

a counterexample wrt both runtime and kolmogorov complexity: 4-coloring