标题： 计数函数的低集 显示英文标题

标题： Low sets for counting functions

摘要： 在本文中，我们表征了对于计数函数类而言低的语言和函数类。 #P 和 GapP 的低类被精确地表征：Low(#P) = UP $\cap$ coUP，而 Low(GapP) = SPP。 我们证明了 Low(TotP) = P，Low(SpanP) = NP $\cap$ coNP，并给出了 #P、GapP、TotP 和 SpanP 的低函数类的表征。 我们建立了 NPSVt、UPSVt 与计数函数类之间的关系。 对于这些类之间的每个包含关系，我们都给出了语言类之间的等价包含关系。 我们还证明了 SpanP $\subseteq$ GapP 当且仅当 NP $\subseteq$ SPP，并且 GapP+ $\subseteq$ SpanP 的包含关系意味着 PH = $\Sigma_{2}^{P}$。 对于 #P、GapP、TotP 和 SpanP 这些类，我们总结了已知的结果，并证明了这些类中的每一个如果且仅如果它坍缩到其函数的低类，则它在 FP+ 左复合下是封闭的。 显示英文摘要

摘要： In this paper, we characterize the classes of languages and functions that are low for counting function classes. The classes #P and GapP have their low classes exactly characterized: Low(#P) = UP $\cap$ coUP and Low(GapP) = SPP. We prove that Low(TotP) = P, Low(SpanP) = NP $\cap$ coNP, and give characterizations of low function classes for #P, GapP, TotP, and SpanP. We establish the relations between NPSVt, UPSVt, and the counting function classes. For each of the inclusions between these classes we give an equivalent inclusion between language classes. We also prove that SpanP $\subseteq$ GapP if and only if NP $\subseteq$ SPP, and the inclusion GapP+ $\subseteq$ SpanP implies PH = $\Sigma_{2}^{P}$. For the classes #P, GapP, TotP, and SpanP we summarize the known results and prove that each of these classes is closed under left composition with FP+ if and only if it collapses to its low class of functions.