Hacker News Reader

I 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/

[2] https://en.wikipedia.org/wiki/NP-hardness#Examples

View on HN

The reductions in your linked paper [1] are not polynomial-time reductions.

Construct 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.

I 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.

Reply on news.ycombinator.com