What do the halting problem and P vs NP say about computing's limits?

The two problems mark two different kinds of limit. The halting problem shows that some questions cannot be answered by any algorithm at all, a limit that has been proved. P versus NP concerns which solvable problems can be solved efficiently, and that question is still unresolved. Most theoretical computer scientists believe P and NP differ, but nobody has a proof. [1] [2]

The halting problem asks whether an arbitrary program, given an input, will eventually finish or run forever. Alan Turing proved in 1937 that no general algorithm can answer this correctly for every program and input pair. It is therefore called undecidable. According to [Wikipedia](https://en.wikipedia.org/wiki/Halting_problem), it shows that some functions are mathematically definable but not computable. [3]

The Stanford Encyclopedia of Philosophy gives the argument in outline. It considers the set of Turing machines that halt when given their own description as input. Assuming that set could be decided leads to a contradiction, so deciding halting is not a computable problem. [4]

There is also an asymmetry. If a program does halt, you can show it by running it and waiting. What cannot be done in general is to decide in advance, for every program, whether it will halt. In this sense deciding a statement is harder than demonstrating it when it is true. [1]

Here the question shifts from what is computable to what is efficiently computable. P is the class of problems with an efficient, polynomial-time solution. NP is the class of problems where a yes answer can be efficiently demonstrated. The question is whether the two classes are the same, which echoes the deciding-versus-demonstrating gap in the halting problem but with efficiency added. [1]

NP-complete problems are the hardest problems in NP. If any one of them had an efficient algorithm, all of them would, and P would equal NP. If any one were shown to have none, P would not equal NP. Thousands of such problems are known, including the travelling salesperson problem and longest paths. [1] [2]

Course notes from Columbia point out that we know for certain some problems have no algorithm, with the halting problem as the example. NP-completeness is weaker evidence. It strongly suggests a problem has no polynomial-time algorithm, but it is not a mathematical proof of that while P versus NP is open. [5]

The practical stakes differ too. OpenStax says an efficient algorithm for any NP-complete problem would help routing, logistics and drug discovery, and would break essentially all modern Internet security and password systems. [2]