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

StackOverflow https://stackoverflow.com/questions/20683988

  •  19-09-2022
  •  | 
  •  

Question

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?

Was it helpful?

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

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top