Can I read On the Conditional Complexity of Sets of Strings on EtoBox?

On the Conditional Complexity of Sets of Strings by Epstein, Samuel is a scholarly article available to read on EtoBox.

What is On the Conditional Complexity of Sets of Strings about?

Given a set X of finite strings, one interesting question to ask is whether there exists a member of X which is simple conditional to all other members of X. Conditional simplicity is measured by low conditional Kolmogorov complexity. We prove the affirmative to this question for sets that have low mutual information with the halting sequence. There are two results with respect to this question. One is dependent on the maximum conditional complexity between two elements of X, the other is dependent on the maximum expected value of the conditional complexity of a member of X relative to each member of X.

Author

Epstein, Samuel

Published

2019

Language

EN