5 ms·
The article contains a misleading description of NP-hardness: > Computing the Kolmogorov complexity for a sequence X of N bits length is an NP-hard problem, si
by hakuseki 5y ago
The article contains a misleading description of NP-hardness:
> Computing the Kolmogorov complexity for a sequence X of N bits length is an NP-hard problem, since the search space of possible programs producing any sequence of length N is growing exponentially with respect to the input size N
NP-hardness would actually mean that any NP problem, e.g. a traveling salesman problem, could be "reduced" within polynomial time to calculating the Kolmogorov Complexity of a given string.
- deleted 5y ago[deleted]
- sean_pedersen 5y agoYes 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.
- dataflow 5y agoI think NP-hard is correct? You can reduce the halting problem and Kolmogorov complexity computation to each other [1], so the question is whether TSP can be reduced to the halting problem. Well, you can reduce SAT to the halting problem (they explain how here [2]) and you can reduce TSP to SAT given they're both NP-complete so... we're done? [1] https://www.nearly42.org/cstheory/halting_to_kolmogorov/ https://www.nearly42.org/cstheory/halting_to_kolmogorov/ [2] https://en.wikipedia.org/wiki/NP-hardness#Examples https://en.wikipedia.org/wiki/NP-hardness#Examples
- hakuseki 5y agoThe reductions in your linked paper [1] are not polynomial-time reductions.
- bennofs 5y agoConstruct a TM which enumerates all possible variable assignments and checks if the SAT problem is satisfied then halts if so. You can construct this TM in polynomial time, and it halts exactly if the SAT problem is satisfiable. So this is a polynomial reduction from SAT to the halting problem.
- hakuseki 5y agoI do not dispute this. My comment was about the linked paper [1] regarding equivalence of the halting problem and Kolmogorov complexity, not the SAT problem.