Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.04110 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914199122214912 |
|---|---|
| author | Ivanashev, Yaroslav |
| author_facet | Ivanashev, Yaroslav |
| contents | A language L is low for a relativizable complexity class C, if C$^L$ = C. For the classes #P, GapP, and SpanP the exact low classes of languages are known: Low(#P) = UP $\cap$ coUP, Low(GapP) = SPP, and Low(SpanP) = NP $\cap$ coNP. In this paper, we prove that Low(TotP) = P, and give characterizations of low function classes for #P, GapP, TotP, and SpanP. In particular, we prove that Low$_f$(#P) = UPSV$_t$ and Low$_f$(SpanP) = NPSV$_t$. We establish the inclusion relations between NPSV$_t$, UPSV$_t$, and the counting function classes by giving for each of these inclusions 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 = $Σ_{2}^{P}$. For the class #P we prove that its closure under left composition with FP$_+$ is equivalent to #P = UPSV$_t$, and for SpanP this closure is equivalent to SpanP = NPSV$_t$. For the classes #P, GapP, TotP, and SpanP we summarize the known results and show that each of these classes is closed under left composition with FP$_+$ if and only if it collapses to its low class of functions. We also prove that a NPTM with a #P oracle can always make at most one query to the oracle without changing the number of accepting paths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04110 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Low Sets and Closure Properties of Counting Function Classes Ivanashev, Yaroslav Computational Complexity A language L is low for a relativizable complexity class C, if C$^L$ = C. For the classes #P, GapP, and SpanP the exact low classes of languages are known: Low(#P) = UP $\cap$ coUP, Low(GapP) = SPP, and Low(SpanP) = NP $\cap$ coNP. In this paper, we prove that Low(TotP) = P, and give characterizations of low function classes for #P, GapP, TotP, and SpanP. In particular, we prove that Low$_f$(#P) = UPSV$_t$ and Low$_f$(SpanP) = NPSV$_t$. We establish the inclusion relations between NPSV$_t$, UPSV$_t$, and the counting function classes by giving for each of these inclusions 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 = $Σ_{2}^{P}$. For the class #P we prove that its closure under left composition with FP$_+$ is equivalent to #P = UPSV$_t$, and for SpanP this closure is equivalent to SpanP = NPSV$_t$. For the classes #P, GapP, TotP, and SpanP we summarize the known results and show that each of these classes is closed under left composition with FP$_+$ if and only if it collapses to its low class of functions. We also prove that a NPTM with a #P oracle can always make at most one query to the oracle without changing the number of accepting paths. |
| title | Low Sets and Closure Properties of Counting Function Classes |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2507.04110 |