On: Kolmogorov Complexity: Extensions and Applications

[sean_pedersen]

Yes I am not aware of any proof on that one. Do you think it will suffice to generalize the statement to just "NP problem" instead?

[gjm11 → sean_pedersen]

I'm pretty sure determining Kolmogorov complexity is not in class NP, and in fact isn't computable.

(You can't just try all possible programs, because some of them never terminate and some others run for a very long time and you can't tell in advance which are which.)

[sean_pedersen → gjm11]

I think you are right, since it entails the Halting problem it is not computable and thus not even in NP.

[sn41 → sean_pedersen]

No, it is uncomputable, not an NP problem.