The Halting Problem is a terrible example of NP-Harder

> NP-hard is the set all problems at least as hard as NP-complete

Im a bit confused by this. I thought NP-complete was the intersection of NP-hard and NP. Maybe this is stating the same?

This [1] diagram from Wikipedia represents you are saying in a visual way. NP-hard and NP-complete are defined as basically an equivalence class modulo an algorithm in P which transforms from one problem to the other. In more human terms both NP-hard and NP-complete are reducible with a polynomial algorithm to another problem from their respective class, making them at least as hard.

The difference between the two classes, again in human terms, is that NP-complete problems are decision problems "Does X have property Y?", while NP-hard problems can include more types - search problems, optimization, etc, making the class NP-hard strictly larger than NP-complete in set terms.

The statement in the article means that NP-hard problems require solving a NP-complete problem plus a P problem - hence being at least as hard.

[1] https://en.m.wikipedia.org/wiki/File:P_np_np-complete_np-har...

If NP-hard isn't even a subset of NP, why is it called "NP-hard"?