No.13336933 ViewReplyOriginalReport
brainlet here, I'm trying to go back through my old comp sci notes to learn shit I didn't really grasp in class. I'm re-learning about NP problems, and NP hardness.
I'm confused by wikipedia though. On NP-Hardness it says this:
>A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H.
But it also says this:
>NP-Hard:
>Class of problems which are at least as hard as the hardest problems in NP...

How are those not contradictions? As I understand it, if every problem in L is reducible to H that means H is equally or less complex than those problems in L. But the second thing says the opposite, that H is equally or more complex as all problems in L.