My naive attempt to make the algorithmic-information-theory variant of the theorem is (I’m pretty sure) false.
That is: I’m pretty sure there’s some f, A, X such that
Sketch: Given some special A’, X’, define f(X,A) = s if X,A=X’,A’ else X, for some easily compressible s; and require that K(A’) - K(A’|X’) > ϵ. Then if the inputs have less than epsilon of algorithmic mutual information, you’d know you didn’t have the special inputs, and so f would spit out X and thus not reduce the complexity.
If we chose our s so that K(s) < K(X’|A’), then we’ll get a counterexample.
I’m pretty sure you should be able to construct X’, A’ that satisfy those two inequalities, but I was struggling with some of the details.
My naive attempt to make the algorithmic-information-theory variant of the theorem is (I’m pretty sure) false.
That is: I’m pretty sure there’s some f, A, X such that
Sketch: Given some special A’, X’, define f(X,A) = s if X,A=X’,A’ else X, for some easily compressible s; and require that K(A’) - K(A’|X’) > ϵ. Then if the inputs have less than epsilon of algorithmic mutual information, you’d know you didn’t have the special inputs, and so f would spit out X and thus not reduce the complexity.
If we chose our s so that K(s) < K(X’|A’), then we’ll get a counterexample.
I’m pretty sure you should be able to construct X’, A’ that satisfy those two inequalities, but I was struggling with some of the details.