3 ms·
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?
by sean_pedersen 5y ago
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 5y agoI'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 5y agoI think you are right, since it entails the Halting problem it is not computable and thus not even in NP.
- sn41 5y agoNo, it is uncomputable, not an NP problem.