Definition. NP-hardness
[np-hard]
Definition. NP-hardness [np-hard]
A Language is NP-hard if it is at least as hard as every problem in , i.e., .
There is nothing in this definition that’s really specific to . We could switch it out for other complexity classes if we’d like.
Note that we don’t require our language to be in ! is NP-hard.