GAP-DEFINABILITY AS A CLOSURE PROPERTY

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.