The names of the classes can be confusing, but ${CLASS}-hard means "no harder than ${CLASS}", not " no easier than ${CLASS}".
So, for instance, every problem in P is NP-hard.
${CLASS}-complete, on the other hand, means that its members are both:
1. ${CLASS}-hard and 2. No easier than any other problem in ${CLASS}.
"NP" itself already means "No harder than NP-complete" [under Karp reduction; Cook reduction perhaps tracks ordinary language "hard" better, but, whatever]. "NP-hard" means "No easier than NP-complete". "NP-complete" means, well, "Exactly as easy as NP-complete" [again, under Karp reduction].
I had based my understanding on images like this one, which is in the article:
https://cdn-images-2.medium.com/max/1800/1*_iqZ21FEdk-A_A0-j...
Which I thought said that everything which is at least as complex as everything in NP was in NP hard.
Thank you for correcting me on that.
Is there a term for "every problem such that being able to solve it in P time would allow you to solve NP problems in P time" (or, whatever is the correct way to phrase that)?
1. A problem is in NP if it is a decision problem and polynomial time verifiable proof exist if the answer is yes.
2. A problem is NP-hard if every problem in NP can be reduced to it in polynomial time.
3. A problem is NP-complete if it is NP-hard and in NP.
Things to note. NP is about decision problem, problems with a yes or no answer. Finding the shortest travelling salesman tour is not NP-complete, it is not even in NP, because it is not a decision problem. And even ignoring that it is not a decision problem, there is also no polynomial time verifiable proof. You could show me your solution but how would I verify that it is indeed the shortest tour without computing the shortest tour myself and comparing it with your solution?
The decision version of the travelling salesman problem - exists a tour with costs less than X - is in NP. It is a decision problem and as proof you can just show me the tour and I can check that it is a valid tour and has costs less than X in polynomial time. Further if there is no tour with costs less than X, then you don't have to be able to proof this to me, only if the answer is yes. How would you proof to me that there is no tour with costs less than X? Decisions problems with proofs if the answer is no are in co-NP. A problem can have proofs in both cases, then it is in the intersection of NP and co-NP.
A problem is NP-hard if you can reduce every problem in NP to it in polynomial time, i.e. if you can solve a NP-hard problem, then you can solve all problems in NP with at most a polynomial slowdown. In other words NP-hard problems are at least as hard as the hardest problems in NP. A NP-hard problem is not required to be a decision problem, does not have to have polynomial time verifiable proof, it does not even have to be decidable.
Finding the shortest travelling salesman tour is NP-hard and an example of not being a decision problem and not having polynomial time verifiable proof. But if you can find the shortest tour, then you can trivially solve the decision version of the travelling salesman problem which is NP-complete. A problem is NP-complete if it is NP-hard and in NP, i.e. NP-complete problems are the NP-hard decision problems with polynomial time verifiable proof if the answer is yes.
This is much closer to what I had thought before I read what procrastitron said (though I was missing a number of the details such as things regarding NP vs co-NP ).
Thanks to you and Chinjut for clearing this up.
Also, this seems like this means that in my first comment my statement of " if you've shown the problem to be in NP, then if it is NP-hard then [it is NP-complete]." was correct? (judging based on your statement that "A problem is NP-complete if it is NP-hard and in NP", which seems to roughly say what I said in my first comment).
Am I correct in thinking that these say basically the same thing?