NP-naming Convention
The NP-family naming system is confusing: NP-hard problems are not all NP, despite having NP as the prefix of their class name. However, the names are now entrenched and unlikely to change. On the other hand, the NP-naming system has some deeper sense, because the NP family is defined in relation to the class NP:
- NP-hard
- At least as hard as the hardest problems in NP. Such problems need not be in NP; indeed, they may not even be decision problems.
- NP-complete
- These are the hardest problems in NP. Such a problem is NP-hard and in NP.
- NP-easy
- At most as hard as NP, but not necessarily in NP, since they may not be decision problems.
- NP-equivalent
- Exactly as difficult as the hardest problems in NP, but not necessarily in NP.
Read more about this topic: NP-hard
Famous quotes containing the word convention:
““We’ll encounter opposition, won’t we, if we give women the same education that we give to men,” Socrates says to Galucon. “For then we’d have to let women ... exercise in the company of men. And we know how ridiculous that would seem.” ... Convention and habit are women’s enemies here, and reason their ally.”
—Martha Nussbaum (b. 1947)