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.
-
Show this thread
Kolmogorov complexity presumes nothing about runtime complexity, so I don't see the link with NP completeness
1:11 PM - 9 Dec 2017
0 replies
0 retweets
2 likes
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.