2025/07/05 by Yaroslav Ivanashev, Ivanashev, Yaroslav · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #cs.CC
paper · pdf · doi:10.48550/arxiv.2507.04110
openalex publication_date 2025/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31 · arxiv created 2026/08/02 · arxiv updated 2026/08/04
A language L is low for a relativizable complexity class C, if CL = C. For the classes #P, GapP, and SpanP the exact low classes of languages are known: Low(#P) = UP ∩ coUP, Low(GapP) = SPP, and Low(SpanP) = NP ∩ 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 Lowf(#P) = UPSVt and Lowf(SpanP) = NPSVt. We establish the inclusion relations between NPSVt, UPSVt, and the counting function classes by giving for each of these inclusions an equivalent inclusion between language classes. We also prove that SpanP ⊆ GapP if and only if NP ⊆ SPP, and the inclusion GapP+ ⊆ SpanP implies PH = Σ2P. For the class #P we prove that its closure under left composition with FP+ is equivalent to #P = UPSVt, and for SpanP this closure is equivalent to SpanP = NPSVt. 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.