3 ms·
The reductions in your linked paper [1] are not polynomial-time reductions.
by hakuseki 5y ago
The 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.