Editing NP-hardness (section)

== NP-naming convention ==
NP-hard problems do not have to be elements of the complexity class NP.
As NP plays a central role in [[Computational complexity theory|computational complexity]], it is used as the basis of several classes:
;[[NP (complexity)|NP]]: Class of computational decision problems for which any given ''yes''-solution can be verified as a solution in polynomial time by a deterministic Turing machine (or ''solvable'' by a ''non-deterministic'' Turing machine in polynomial time).
;NP-hard: Class of problems which are at least as hard as the hardest problems in NP. Problems that are NP-hard do not have to be elements of NP; indeed, they may not even be decidable.
;[[NP-complete]]: Class of decision problems which contains the hardest problems in NP. Each NP-complete problem has to be in NP.
;[[NP-easy]]: At most as hard as NP, but not necessarily in NP.
;[[NP-equivalent]]: Decision problems that are both NP-hard and NP-easy, but not necessarily in NP.
;[[NP-intermediate]]: If P and NP are different, then there exist decision problems in the region of NP that fall between P and the NP-complete problems. (If P and NP are the same class, then NP-intermediate problems do not exist because in this case every NP-complete problem would fall in P, and by definition, every problem in NP can be reduced to an NP-complete problem.)