Search code examples
algorithmcomplexity-theorynp

Why P=NP does not imply that halting of Turing machine solvable in polynomial time?

I read somewhere that -if some how someone someday can prove that P=NP then we cannot say that halting problem is solvable in polynomial time. Can you please explain why?

Solution

  • Because the halting problem is proven to be not solvable at all.

    So any speed improvements obviously will not make it easier to solve