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.
-
-
Would the proof of Fermat's last theorem, in HOL, compressed, be much larger than the minimum amount of code required to define a HOL theorem proving environment?
-
1/ My claim that it would be. But I have not tried. The theorem introduces many complex concepts and is not a matter of combinatorial
- Show replies
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.