GAP-DEFINABLE COUNTING CLASSES

The function class #P lacks an important closure property: it is not closed under subtraction. To remedy this problem, we introduce the function class GapP as a natural alternative to #P. GapP is the closure of #P under subtraction and has all the other useful closure properties of #P as well. We show that most previously studied counting classes, including PP, C=P, and ModkP, are “gap-definable,” i.e., definable using the values of GapP functions alone. We show that there is a smallest gap-definable class, SPP, which is still large enough to contain Few. We also show that SPP consists of exactly those languages low for GapP, and thus SPP languages are low for any gap-definable class. These results unify and improve earlier disparate results of J. Cai and L. Hemachandra (Math. Systems Theory 23, No. 2 (1990), 95-106) and J. Köbler et al. (J. Comput. System Sci. 44, No. 2 (1992), 272-286). We show further that any countable collection of languages is contained in a unique minimum gap-definable class, which implies that the gap-definable classes form a lattice under inclusion. Subtraction seems necessary for this result, since nothing similar is known for the #P-definable classes. © 1994 by Academic Press, Inc.