A complexity class is given by a membership predicate and a hardness predicate on decision problems over arbitrary relational vocabularies. The classes of this development are built from their membership predicate alone, with hardness read cofinally: a problem $P$ is hard when every member of the class reduces, by a relativized ordered first-order reduction, to every problem that $P$ itself reduces to. This is equivalent to the usual “every member reduces to $P$” (stated in NP is a complexity class), and is the form the library this submission comes from uses. A problem is complete for a class when it belongs to it and is hard for it.

NP is the class whose members are the $\Sigma_1$-definable problems, by Fagin's theorem; more generally the level $\Sigma_{k+1}$ of the polynomial hierarchy has the $\Sigma_{k+1}$-definable problems as members. The library this submission comes from makes closure under first-order reductions part of the definition of a class; that NP is closed is stated separately, in NP is a complexity class.