Gap-definability as a closure property

Gap-definability and the gap-closure operator were defined in [FFK91]. Few complexity classes were known at that time to be gap-definable. In this paper, we give simple characterizations of both gap-definability and the gap-closure operator, and we show that many complexity classes are gap-definable, including P#P, \(P^{\# P_{[1]} }\), PSPACE, EXP, NEXP, MP, and BP·⊕P. If a class is closed under union, intersection and contains λ and Σ*, then it is gap-definable if and only if it contains SPP; its gap-closure is the closure of this class together with SPP under union and intersection. On the other hand, we give some examples of classes which are reasonable gap-definable but not closed under union (resp. intersection, complement). Finally, we show that a complexity class such as PP or PSPACE, if it is not equal to SPP, contains a maximal proper gap-definable subclass which is closed under many-one reductions.