Low Sets and Closure Properties of Counting Function Classes

Yaroslav Ivanashev · 2025

Read Low Sets and Closure Properties of Counting Function Classes by Yaroslav Ivanashev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04110.txt.

Introduction

Yaroslav Ivanashev, a solo author, studies which problem sets are low for classes that count solutions, a term that means adding the set as a helper does not make the class stronger. For three classic counting classes, the exact low sets were already known.

Ivanashev proves the low set for a further counting class is just the class of easy problems. He also gives the low classes for functions, not just sets, for four counting classes. Links between those function results and set results are set out as equal claims. The work ties up when each class stays closed under a kind of composition.

Catalog record

CREATORYaroslav Ivanashev
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04110

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Low Sets and Closure Properties of Counting Function Classes Yaroslav Ivanashev Abstract A language L L is low for a relativizable complexity class C C , if it doesn’t increase the computational power of a class when it is used as an oracle: C L = C C^{L}=C . For the classes # ​ 𝖯 \mathsf{\#P} , 𝖦𝖺𝗉𝖯 \mathsf{GapP} , and 𝖲𝗉𝖺𝗇𝖯 \mathsf{SpanP} low classes of languages are known: L ​ o ​ w ​ ( # ​ 𝖯 ) = 𝖴𝖯 ∩ 𝖼𝗈𝖴𝖯 Low(\mathsf{\#P})=\mathsf{UP}\cap\mathsf{coUP} , L ​ o ​ w ​ ( 𝖦𝖺𝗉𝖯 ) = 𝖲𝖯𝖯 Low(\mathsf{GapP})=\mathsf{SPP} , and L ​ o ​ w ​ ( 𝖲𝗉𝖺𝗇𝖯 ) = 𝖭𝖯 ∩ 𝖼𝗈𝖭𝖯 Low(\mathsf{SpanP})=\mathsf{NP}\cap\mathsf{coNP} . In this paper, we prove that L ​ o ​ w ​ ( 𝖳𝗈𝗍𝖯 ) = 𝖯 Low(\mathsf{TotP})=\mathsf{P} , and give characterizations of low function classes for # ​ 𝖯 \mathsf{\#P} , 𝖦𝖺𝗉𝖯 \mathsf{GapP} , 𝖳𝗈𝗍𝖯 \mathsf{TotP} , and 𝖲𝗉𝖺𝗇𝖯 \mathsf{SpanP} . We establish the relations between 𝖭𝖯𝖲𝖵 𝗍 \mathsf{NPSV_{t}} , 𝖴𝖯𝖲𝖵 𝗍 \mathsf{UPSV_{t}} , 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 𝖲𝗉𝖺𝗇𝖯 ⊆ 𝖦𝖺𝗉𝖯 \mathsf{SpanP}\subseteq\mathsf{GapP} if and only if 𝖭𝖯 ⊆ 𝖲𝖯𝖯 \mathsf{NP}\subseteq\mathsf{SPP} , and the inclusion 𝖦𝖺𝗉𝖯 + ⊆ 𝖲𝗉𝖺𝗇𝖯 \mathsf{GapP_{+}}\subseteq\mathsf{SpanP} implies 𝖯𝖧 = Σ 𝟤 𝖯 \mathsf{PH}=\mathsf{\Sigma^{P}_{2}} . For the classes # ​ 𝖯 \mathsf{\#P} , 𝖦𝖺𝗉𝖯 \mathsf{GapP} , 𝖳𝗈𝗍𝖯 \mathsf{TotP} , and 𝖲𝗉𝖺𝗇𝖯 \mathsf{SpanP} we summarize the known results and prove that each of these classes is closed under left composition with 𝖥𝖯 + \mathsf{FP_{+}} if and only if it collapses to its low class of functions. HSE University, Faculty of Computer Science, Moscow, 101000, [email protected]://orcid.org/0009-0001-5059-1844 ccs Theory of computation Complexity classes keywords Computational complexity, counting classes, closure properties, lowness † † runningauthor: Y. Ivanashev † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The concept of lowness in complexity theory was introduced by Schöning to describe the languages in \mathsf{NP} that are low for the levels of polynomial-time hierarchy [ 18 ] . A language L is low for a relativizable complexity class C , if C^{L}=C . Informally, a language is low if it doesn’t increase the computational power of a class when it is used as an oracle. Some complexity classes have their low classes exactly characterized. For example, Low(\mathsf{NP})=\mathsf{NP}\cap\mathsf{coNP} [ 18 ] , Low(\mathsf{AM})=\mathsf{AM}\cap\mathsf{coAM} [ 19 ] , and Low(\mathsf{BPP})=\mathsf{BPP} [ 27 ] . For counting function classes \mathsf{\#P} [ 25 ] , \mathsf{GapP} [ 5 ] , and \mathsf{SpanP} [ 13 ] the low classes are also known: Low(\mathsf{\#P})=\mathsf{UP}\cap\mathsf{coUP} [ 15 ] , Low(\mathsf{GapP})=\mathsf{SPP} [ 5 ] and Low(\mathsf{SpanP})=\mathsf{NP}\cap\mathsf{coNP} [ 24 ] . In this paper, we give characterizations of a low language class for \mathsf{TotP} [ 12 ] and low function classes for \mathsf{\#P} , \mathsf{GapP} , \mathsf{GapP_{+}} , \mathsf{TotP} , and \mathsf{SpanP} . The results are summarized in Table 1 . In particular, we show that \mathsf{UPSV_{t}} = Low_{f}(\mathsf{\#P}) and \mathsf{NPSV_{t}} = Low_{f}(\mathsf{SpanP}) . The classes \mathsf{NPSV_{t}} and \mathsf{UPSV_{t}} are the subclasses of \mathsf{NPSV} and \mathsf{UPSV} respectively, that contain only total functions [ 3 , 4 ] . In section 4 , we establish the relations between the classes \mathsf{NPSV_{t}} , \mathsf{UPSV_{t}} , and the counting function classes \mathsf{\#P} , \mathsf{GapP_{+}} , \mathsf{TotP} , and \mathsf{SpanP} . We characterize all inclusions between these classes in terms of inclusions between language classes. In section 2 , we establish the relations between classes \mathsf{GapP} and \mathsf{SpanP} . We prove that \mathsf{SpanP}\subseteq\mathsf{GapP} if and only if \mathsf{NP}\subseteq\mathsf{SPP} , and the inclusion \mathsf{GapP_{+}}\subseteq\mathsf{SpanP} implies \mathsf{PH}=\mathsf{\Sigma^{P}_{2}} . The latter result implies that the inclusion \mathsf{\#P}\subseteq\mathsf{GapP_{+}} is proper unless \mathsf{PH}=\mathsf{\Sigma^{P}_{2}} . In section 5 , we study the closure of counting function classes under left composition with \mathsf{FP_{+}} . In [ 17 ] , it is shown that the closure of \mathsf{\#P} under composition with multivariate \mathsf{FP_{+}} -functions is equivalent to \mathsf{PP}=\mathsf{UP} , and for \mathsf{SpanP} this closure is equivalent to \mathsf{P}^{\mathsf{PP}}=\mathsf{NP} (in [ 26 ] , this statement is extended to \mathsf{PP}=\mathsf{NP} ). We show that in these theorems univariate \mathsf{FP_{+}} -functions can be considered, and the closure of \mathsf{\#P} is also equivalent to \mathsf{\#P}=\mathsf{UPSV_{t}} . For \mathsf{SpanP} , this closure is equivalent to \mathsf{SpanP}=\mathsf{NPSV_{t}} . Analogous theorems for \mathsf{GapP} [ 21 , 7 , 5 ] and \mathsf{TotP} [ 11 ] are also known. Table 1 summarizes the results, which show that each of the classes \mathsf{\#P} , \mathsf{GapP} , \mathsf{GapP_{+}} , \mathsf{TotP} , and \mathsf{SpanP} is closed under left composition with \mathsf{FP_{+}} if and only if it coincides with its low class of functions. In section 6 , we prove an auxiliary lemma, which shows that a composition of counting functions with multivariate \mathsf{FP} -functions is the same as a composition with univariate \mathsf{FP} -functions. We use this result in section 5 . By a similar argument, we prove that a NPTM with a \mathsf{\#P} oracle can always make at most one query to the oracle preserving the same number of accepting paths. Class Low languages Low functions Closure under composition with \mathsf{FP} is equivalent to \mathsf{\#P} \mathsf{UP}\cap\mathsf{coUP} \mathsf{UPSV_{t}} \mathsf{\#P}=\mathsf{UPSV_{t}} \mathsf{PP}=\mathsf{UP} \mathsf{GapP} \mathsf{SPP} \mathsf{FP}^{\mathsf{SPP}} \mathsf{GapP}=\mathsf{FP}^{\mathsf{SPP}} \mathsf{PP}=\mathsf{SPP} \mathsf{GapP_{+}} \mathsf{SPP} \mathsf{FP}^{\mathsf{SPP}} \mathsf{GapP_{+}}=\mathsf{FP_{+}}^{\mathsf{SPP}} \mathsf{PP}=\mathsf{SPP} \mathsf{TotP} \mathsf{P} \mathsf{FP} \mathsf{TotP}=\mathsf{FP_{+}} \mathsf{PP}=\mathsf{P} \mathsf{SpanP} \mathsf{NP}\cap\mathsf{coNP} \mathsf{NPSV_{t}} \mathsf{SpanP}=\mathsf{NPSV_{t}} \mathsf{PP}=\mathsf{NP} Table 1: 2 Preliminaries In this paper, we use standard notions of a deterministic and nondeterministic Turing machine. Below we give definitions of function and language classes that we will consider: Definition 1 . 1. [ 25 ] \mathsf{\#P}=\{acc_{M}\ |\ M is a NPTM \} , where acc_{M}(x) is the number of accepting paths of M on input x\in\Sigma^{*} . 2. [ 5 ] \mathsf{GapP}=\{gap_{M}\ |\ M is a NPTM \} , where gap_{M}(x)=acc_{M}(x)-rej_{M}(x) and rej_{M}(x) is the number of rejecting paths of M on input x\in\Sigma^{*} . 3. [ 12 ] \mathsf{TotP}=\{tot_{M}\ |\ M is a NPTM \} , where tot_{M}(x)=Total_{M}(x)-1 and Total_{M}(x) is the number of all paths of M on input x\in\Sigma^{*} . 1 1 1 The ”-1” in the definition of \mathsf{TotP} allows these functions to take a zero value. A predicate based definition of \mathsf{TotP} is given in [ 11 ] . 4. [ 13 ] \mathsf{SpanP}=\{span_{M}\ |\ M is a NPTM \} , where span_{M}(x) is the number of distinct outputs on accepting paths of M on input x\in\Sigma^{*} . 5. \mathsf{FP}=\{f:\Sigma^{*}\rightarrow\mathbb{Z}\ |\ f is computable in polynomial time \} . \mathsf{FP_{+}} and \mathsf{GapP_{+}} are the subsets of \mathsf{FP} and \mathsf{GapP} respectively, that contain only non-negative valued functions. Definition 2 . 1. The class \mathsf{NP} consists of all languages L for which there exists a function f\in\mathsf{\#P} such that for any x\in\Sigma^{*} : \displaystyle x\in L\Leftrightarrow f(x)>0. 2. The class \mathsf{UP} consists of all languages L for which there exists a function f\in\mathsf{\#P} such that for any x\in\Sigma^{*} : \displaystyle x\in L\Leftrightarrow f(x)=1, \displaystyle x\notin L\Leftrightarrow f(x)=0. 3. The class \mathsf{C_{=}P} consists of all languages L for which there exist functions f\in\mathsf{\#P} and g\in\mathsf{FP}

Read the complete text