Such a link would be especially interesting with regard to the development of "general" AI
Show this thread
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.
-
-
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
You might consider the law of requisite variety.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
The more difficult it is to specify the more resources that need to be spent specifying it in a solvable form. Would make sense
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
Kolmogorov complexity presumes nothing about runtime complexity, so I don't see the link with NP completeness
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
Fermat’s last theorem
-
A theorem is not a task. Proving it is the task. Specifying that task requires a way to check correctness and a way to define the symbols used -- i.e. a theorem proving environment, which is high KC, comparable to long proofs
- Show replies
New conversation -
-
-
What about Fermat’s last theorem - a clear counter example. Riemann’s hypothesis may be another counter example
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
I must be missing something in your question. If P is a problem with a countable solution space S, and A : S -> {0, 1} is a function that verifies if x is a solution of P, then solving P is just looping over S and applying A to every element.
-
So the Kolmogorov complexity of solving P is the sum of the complexity of A and the complexity of enumerating S. If S is the natural, the complexity of enumerating S is finite, but the complexity of its elements is unbounded.
- Show replies
New conversation -
-
-
Wouldn't the KC of any problem with a verifiable solution be upper bounded by the KC of the checker plus KC of random search?
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
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.