Gap-definability and the gap closure operator were defined by S. Fenne
r, L. Fortnow and S. Kurth (J. Comput. System Sci. 48, 116-148 (1994))
. Few complexity classes were known at that time to be gap-definable.
In this paper, we give simple characterizations of both gap-definabili
ty and the gap-closure operator, and we show that many complexity clas
ses are gap-definable, including P#(P), P#(P[1]), PSPACE, EXP, NEXP, M
P (Middle-bit P), and BP . + P. If a class is closed under union and i
ntersection and contains circle divide and Sigma, then it is gap-defi
nable if and only if it contains SPP; its gap-closure is the closure o
f this class together with SPP under union and intersection. On the ot
her hand, we give some examples of classes which are reasonable and ga
p-definable but not closed under union (resp. intersection, complement
). Finally, we show that a complexity class such as PSPACE or PP, if i
t is not equal to SPP, contains a maximal gap-definable many-one reduc
tion-closed subclass, which is properly between SPP and the class of a
ll PSPACE-incomplete (PP-incomplete) sets with respect to containment.
The gap-closure of the class of all incomplete sets in PSPACE (resp.
PP) is PSPACE (resp. PP). (C) 1996 Academic Press, Inc.