Gap-deenable Counting Classes
Gap-deenable Counting Classes
复制标题
可消除间隙的计数类
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Stephen A. Fenner
中科院分区：
文献类型：
--
作者：
Stephen A. Fenner;Lance J. Fortnowy;S. Kurtz;Stephen A. Fenner
函数类#P缺乏重要的封闭属性：在减法下未关闭。为了解决这个问题，我们将功能类GAPP作为#P的自然替代品。 GAPP是在减法下的#P的关闭，并且还具有#P的所有其他有用的闭合属性。我们表明，大多数先前研究的计数类，包括pp，c = p和modkp，是\ gap-de nable的，即使用GAPP函数的值。班级，仍然足够大，我们还表明SPP完全由较低的语言组成，因此，对于任何GAP-DE Nable类，SPP语言都很低统一并改善了CAI和Hemachandra [7]和K Obler，Sch Oning，Toda和Tor AN [15]的统一结果[15]。 ，这意味着在包含的差距中，差距为晶格似乎是必不可少的
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-de nable," i.e., de nable using the values of GapP functions alone. We show that there is a smallest gap-de nable 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-de nable class. These results unify and improve earlier disparate results of Cai & Hemachandra [7] and K obler, Sch oning, Toda, & Tor an [15]. We show further that any countable collection of languages is contained in a unique minimumgap-de nable class, which implies that the gap-de nable classes form a lattice under inclusion. Subtraction seems necessary for this result, since nothing similar is known for the #P-de nable classes. 3