{"id":"36ee1b5c-5e0c-4f12-bc20-0bb545ba8741","arxiv_id":"2507.04110","paper_version":5,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives exact characterizations of low languages and low functions for the counting classes TotP, #P, GapP, and SpanP, and links their closure under composition to collapses such as PP=UP and PP=NP.","lead":"Some computation problems are about counting possible answers. This paper studies when allowing a machine to ask a 'counting oracle' adds no extra power, and it finds exact answers for several classes of such machines. The results connect these oracle properties to open questions about whether two well-known complexity classes are the same.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's weakest_assumption points to Proposition 2.8 and the claim that polynomial-bounded TotP functions lie in FP. I checked both: the TotP claim is correct because a polynomial leaf count forces the whole computation tree to have polynomially many nodes, so enumeration runs in polynomial time; the NPSV_t/UPSV_t identities are standard and hold for total functions with polynomial-bounded outputs via the pregraph construction and witness-guessing simulations. The central lowness proofs in Theorem 3.3 are structurally sound; the only missing material is the four 'similar' cases, which follow the #P template. Theorems 5.1 and 5.2 are the most substantive part. Their proofs rely on Lemma 6.1 to identify one-query FP+ computations with FP+∘#P / FP+∘SpanP. This is correct once one notes that the input x can be encoded into a #P function and that #P/SpanP are closed under the required packing operations; the paper does not spell this out, but the gap is fillable. Corollary 6.4's equality chain is under-justified, especially the C=P/PP one-query steps, but those steps can be recovered by guessing the oracle value/certificate and using a single equality check. Thus I do not see a fatal flaw in the central claim: the conditional verdict is appropriate pending the missing details, but no deeper correction is required.","tokens_in":8573,"tokens_out":52288,"duration_ms":597332,"concrete_test":"Independently derive f∈FP^{UP∩coUP} ⇒ f∈UPSV_t for a total integer-valued f with polynomial-bounded output: construct the pregraph language, prove it is in UP∩coUP, and verify that binary search with this oracle computes f. If this derivation fails under the paper's exact definitions, then Proposition 2.8—and hence Low_f(#P)=UPSV_t—would be unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing concern with the central claims. The key identities UPSV_t=FP^{UP∩coUP} and NPSV_t=FP^{NP∩coNP} (Proposition 2.8) are standard and survive the total/polynomial-output boundary case: total single-valued machines give pregraph languages in UP∩coUP and NP∩coNP respectively, and conversely oracle machines can be simulated by guessing the unique (or at least one) accepting witness. The proof of Low(TotP)=P relies on the solid fact that polynomial-bounded TotP functions are in FP. Theorems 5.1 and 5.2 are sound modulo fillable packing/encoding arguments, and the oracle-equality chain in Corollary 6.4 can be justified by guess-and-verify reductions. The paper's real soft spots are presentation gaps—the four omitted 'similar' cases in Theorem 3.3, the unstated reduction from one-query FP+ machines to univariate FP+∘#P composition, and the unproved Corollary 6.4 chain—but none of these threatens the correctness of the central lowness and closure characterizations.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies lowness for counting function classes. It proves Low(TotP)=P, gives characterizations Low_f(#P)=UPSV_t and Low_f(SpanP)=NPSV_t, establishes inclusion relations between NPSV_t, UPSV_t, and the counting classes #P, GapP+, TotP, SpanP, and shows that closure under left composition with FP+ is equivalent to collapse to the corresponding low function class (e.g., PP=UP for #P, PP=NP for SpanP). The central proofs for Low(TotP)=P, Theorem 3.3(1), Theorems 5.1-5.2, and Proposition 6.3 are clean and internally consistent. However, several load-bearing statements are only asserted as 'similar' or without proof, and the FP+ variant of the composition lemma is not stated explicitly.","tokens_in":8779,"tokens_out":20716,"duration_ms":217088,"significance":"If correct, the paper provides a complete picture of low function classes for #P, GapP, GapP+, TotP, and SpanP, and connects closure under FP+ composition to well-known collapses (PP=UP, PP=NP, PP=SPP, PP=P). The main constructions are standard and the proofs that are actually given are sound. The paper explicitly relies on known identities (UPSV_t=FP^{UP∩coUP}, NPSV_t=FP^{NP∩coNP}) and on the cited fact that polynomial-bounded TotP functions are in FP; both are appropriate. The contribution is significant for researchers working on counting classes and lowness, but the current manuscript has presentation gaps that must be fixed before the results are fully supported.","major_comments":[{"comment":"The proof of Theorem 3.3 is given only for case (1), #P; cases (2)-(5), namely Low_f(GapP)=FP^{SPP}, Low_f(GapP+)=FP^{SPP}, Low_f(TotP)=FP, and Low_f(SpanP)=NPSV_t, are asserted to be 'similar' without proof. These cases are central to Table 1 and to the paper's main claims. Please provide complete proofs for these cases, or at minimum a detailed proof for a representative case (e.g., GapP) showing how the pregraph argument and the corresponding language lowness theorem (Theorem 3.2) combine, and state explicitly any differences for TotP and SpanP. In particular, for Low_f(GapP)=FP^{SPP} one must show both FP^{SPP}⊆Low_f(GapP) (using Low(GapP)=SPP) and that a low function has pregraph in SPP.","section":"Theorem 3.3"},{"comment":"The proofs of (1⇒3) in Theorems 5.1 and 5.2 use the identity FP_+^{#P[1]} = FP_+∘#P (and its SpanP analogue), invoking Lemma 6.1/Corollary 6.2. However, Lemma 6.1 is stated and proved for FP, not for FP_+; it is not immediate that the reduction preserves nonnegativity of the outer function. Please state and prove the FP_+ variant explicitly, or explain how the existing proof is adapted without losing nonnegativity.","section":"Theorems 5.1 and 5.2"},{"comment":"Corollary 6.4 asserts a chain of oracle equalities (e.g., NP^{C=P[1]} = NP^{PP} = NP^{#P} and PP^{C=P[1]} = PP^{PP}) without proof or citation. Since these equalities are not derived in the text, either add a proof or a reference for each non-obvious equality, or revise the corollary so that it states only what follows directly from Proposition 6.3.","section":"Corollary 6.4"},{"comment":"The proofs of Proposition 4.2 and Proposition 4.4 are only sketched, with the left-to-right directions described as 'similar' to Proposition 4.1. Since these propositions are used later in the inclusion characterizations and in Table 1, please provide at least the details for one of the cases (e.g., NPSV_t⊆#P) and state the required oracle constructions for the other cases.","section":"Propositions 4.2 and 4.4"}],"minor_comments":[{"comment":"The notation 'FPSPP' appears without superscripts; clarify whether it means FP^{SPP} and whether the + variant is intended for GapP+ in the low-functions column.","section":"Table 1"},{"comment":"The classes NPSV_t and UPSV_t are defined for functions with polynomial-bounded output, but Section 4 later restricts them to nonnegative integer-valued functions; this restriction should be stated where it is first needed.","section":"Definition 2.7"},{"comment":"In Lemma 6.1, the statement that the same composition lemma holds for GapP, TotP, and SpanP is only given verbally; since GapP functions may be negative, the concatenation encoding needs a signed representation or an explicit reduction to the #P case.","section":"Lemma 6.1"},{"comment":"The notation NP^{C=P[1]}, PP^{C=P[1]}, etc. is not defined in the paper; please define what 'one query' means for language oracles, or avoid the notation.","section":"Corollary 6.4"},{"comment":"There are several formatting issues, such as 'Σ P 2' for Σ_2^P and 'FP SPP' for FP^{SPP}; these should be cleaned up in the final version.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is in scope for a computational complexity journal. The main results appear correct, but the number of 'similar proof' statements is high for a paper whose headline contribution is Table 1; the revision should fill these in. The self-citation [14] is used only for the TotP closure theorem (Theorem 5.5), not for the central new theorems, so there is no circularity concern. The reliance on external facts (e.g., [2], [4]) is acceptable, though the paper would benefit from stating these premises explicitly rather than only citing them."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Low(TotP)=P is the headline new result, and it has a genuinely clean proof: if L is low for TotP then its characteristic function is in TotP^L = TotP, and since polynomial-bounded TotP functions are in FP, L is in P. That argument checks out.\n\nThe paper also gives explicit low-function characterizations Low_f(#P)=UPSV_t and Low_f(SpanP)=NPSV_t, and connects closure under left composition with FP_+ to collapse conditions (#P=UPSV_t iff PP=UP, SpanP=NPSV_t iff PP=NP). These are useful and mostly proved directly. Table 1 is a nice organizing device. Proposition 6.3, the single-query #P oracle lemma, is a small adaptation of existing work but the proof is clean and the lemma is a handy tool.\n\nThe soft spots are real but presentational. Theorem 3.3 announces five characterizations but the proof only works through case (1); the other four are dismissed as 'similar'. Given that the paper's main selling point is these characterizations, that is a gap. The same pattern repeats in Proposition 4.4 and the proof of Theorem 5.4. Corollary 6.4 just asserts a chain of oracle equalities (NP^#P = NP^PP = ... ) with no derivation or citation; those probably all go through by standard guess-and-verify reductions, but they are exactly what a referee should check.\n\nThe dependency on UPSV_t = FP^{UP∩coUP} and NPSV_t = FP^{NP∩coNP} is standard; I do not think the total/output-boundary conditions cause trouble. The self-citation to [14] is not load-bearing, since the TotP closure theorem is cited rather than re-derived and the other main results are proved directly.\n\nBottom line: the central results look correct, the presentation is rougher than it should be for the claims made. This deserves a serious referee, not a desk rejection, but the referee should ask for the 'similar' proofs to be spelled out and Corollary 6.4 to be justified.","headline":"Low(TotP)=P and the low-function characterizations for #P and SpanP look right; the paper needs fuller proofs for the 'similar' cases but is worth refereeing.","tokens_in":9326,"tokens_out":2321,"would_cite":true,"duration_ms":25221,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Low(TotP)=P and the low functions for #P and SpanP are exactly the total single-valued function classes UPSV_t and NPSV_t.","keywords":["computational complexity","counting classes","lowness","closure properties","#P","GapP","SpanP","TotP"],"falsifier":"One concrete test: look for a total function $f$ with polynomial-bounded output that lies in $\\mathrm{UPSV}_t$ but not in $\\mathrm{FP}^{\\mathrm{UP}\\cap\\mathrm{coUP}}$; if such a function exists, $\\mathrm{Low}_f(\\#\\mathrm{P})=\\mathrm{UPSV}_t$ fails. Alternatively, a language $L\\notin\\mathrm{P}$ with $\\mathrm{TotP}^L=\\mathrm{TotP}$ would refute $\\mathrm{Low}(\\mathrm{TotP})=\\mathrm{P}$.","tokens_in":2927,"feed_emoji":"🧮","tokens_out":3270,"duration_ms":174867,"temperature":0.7,"pith_summary":"The paper proves precise lowness results for the counting function classes $\\#\\mathrm{P}$, $\\mathrm{GapP}$, $\\mathrm{GapP}_+$, $\\mathrm{TotP}$, and $\\mathrm{SpanP}$. Its headline equalities are $\\mathrm{Low}(\\mathrm{TotP})=\\mathrm{P}$, $\\mathrm{Low}_f(\\#\\mathrm{P})=\\mathrm{UPSV}_t$, $\\mathrm{Low}_f(\\mathrm{SpanP})=\\mathrm{NPSV}_t$, $\\mathrm{Low}_f(\\mathrm{TotP})=\\mathrm{FP}$, and $\\mathrm{Low}_f(\\mathrm{GapP})=\\mathrm{Low}_f(\\mathrm{GapP}_+)=\\mathrm{FP}^{\\mathrm{SPP}}$. It also proves that each of these five classes is closed under left composition with $\\mathrm{FP}_+$ exactly when it collapses to its low function class, matching the familiar conditions $\\mathrm{PP}=\\mathrm{UP}$, $\\mathrm{PP}=\\mathrm{SPP}$, $\\mathrm{PP}=\\mathrm{P}$, and $\\mathrm{PP}=\\mathrm{NP}$. Inclusions among the function classes are characterized by language-class inclusions, notably $\\mathrm{SpanP}\\subseteq\\mathrm{GapP}$ iff $\\mathrm{NP}\\subseteq\\mathrm{SPP}$, and $\\mathrm{GapP}_+\\subseteq\\mathrm{SpanP}$ forces $\\mathrm{PH}=\\Sigma_2^{\\mathrm{P}}$. These results matter because they convert questions about which oracles are useless for counting classes into questions about well-known language-class collapses.","feed_headline":"Low(TotP)=P and the low functions of #P and SpanP are exact","feed_subtitle":"Closure under composition with positive feasible functions collapses exactly when PP equals UP, SPP, P, or NP.","key_machinery":"The central objects are the total single-valued function classes $\\mathrm{NPSV}_t$ and $\\mathrm{UPSV}_t$: total functions produced by a nondeterministic polynomial-time machine that has at least one accepting path on every input, or exactly one in the $\\mathrm{UPSV}_t$ case, with all accepting paths printing the same value. The load-bearing identities are $\\mathrm{NPSV}_t = \\mathrm{FP}^{\\mathrm{NP}\\cap\\mathrm{coNP}}$ and $\\mathrm{UPSV}_t = \\mathrm{FP}^{\\mathrm{UP}\\cap\\mathrm{coUP}}$. The paper couples these with the pregraph of a function, $\\{(x,y) : y \\text{ is a prefix of } f(x)\\}$, so that lowness of $f$ for $\\#\\mathrm{P}$ becomes membership of the pregraph in $\\mathrm{UP}\\cap\\mathrm{coUP}$. A technical lemma shows that composition with multivariate $\\mathrm{FP}_+$ functions reduces to composition with univariate ones, and that any machine with a $\\#\\mathrm{P}$ oracle can be simulated by one making a single oracle query while preserving the accepting-path count.","core_discovery":"On the paper's own terms, the central discovery is that lowness for counting function classes is captured by the total single-valued function classes $\\mathrm{UPSV}_t$ and $\\mathrm{NPSV}_t$, and that closure under feasible left composition forces collapse. A language is low for $\\mathrm{TotP}$ exactly when it is in $\\mathrm{P}$. A function is low for $\\#\\mathrm{P}$ exactly when it belongs to $\\mathrm{UPSV}_t$, and low for $\\mathrm{SpanP}$ exactly when it belongs to $\\mathrm{NPSV}_t$; the low function classes for $\\mathrm{GapP}$ and $\\mathrm{GapP}_+$ are both $\\mathrm{FP}^{\\mathrm{SPP}}$, and $\\mathrm{Low}_f(\\mathrm{TotP})=\\mathrm{FP}$. For $\\#\\mathrm{P}$, $\\mathrm{GapP}$, $\\mathrm{GapP}_+$, $\\mathrm{TotP}$, and $\\mathrm{SpanP}$, the paper shows that closure under left composition with $\\mathrm{FP}_+$ is equivalent to equality with the corresponding low function class, and hence to $\\mathrm{PP}=\\mathrm{UP}$, $\\mathrm{PP}=\\mathrm{SPP}$ (twice), $\\mathrm{PP}=\\mathrm{P}$, or $\\mathrm{PP}=\\mathrm{NP}$. The paper further proves $\\mathrm{SpanP}\\subseteq\\mathrm{GapP}$ iff $\\mathrm{NP}\\subseteq\\mathrm{SPP}$, and that $\\mathrm{GapP}_+\\subseteq\\mathrm{SpanP}$ implies $\\mathrm{PH}=\\Sigma_2^{\\mathrm{P}}$.","pith_inferences":["Extension: The uniform pattern in Table 1 suggests a template: for counting classes defined by an NPTM acceptance functional, closure under left composition with $\\mathrm{FP}_+$ may be equivalent to equality with the low function class; testing further counting classes against this template would be a direct next step.","Extension: The single-query lemma for $\\#\\mathrm{P}$ oracles may imply that oracle hierarchies built on $\\#\\mathrm{P}$ collapse to level one, giving normal forms for $\\mathrm{P}^{\\#\\mathrm{P}}$ computations.","Extension: Because the equivalences tie syntactic closure to open language-class collapses, one explicit construction of an $\\mathrm{FP}_+\\circ\\#\\mathrm{P}$ function outside $\\#\\mathrm{P}$ would separate $\\mathrm{UP}$ from $\\mathrm{PP}$; conversely, proving $\\mathrm{PP}=\\mathrm{UP}$ would give a normal form for $\\#\\mathrm{P}$ under composition."],"forward_implications":["If the main theorems are right, the exact functions that are useless as oracles for $\\#\\mathrm{P}$ are the total unambiguous single-valued functions, and the useless functions for $\\mathrm{SpanP}$ are the total nondeterministic single-valued functions.","Closure of $\\#\\mathrm{P}$ under left composition with $\\mathrm{FP}_+$ is equivalent to $\\mathrm{PP}=\\mathrm{UP}$, and closure of $\\mathrm{SpanP}$ under the same operation is equivalent to $\\mathrm{PP}=\\mathrm{NP}$.","$\\mathrm{SpanP}\\subseteq\\mathrm{GapP}$ holds exactly when $\\mathrm{NP}\\subseteq\\mathrm{SPP}$, so the function-class inclusion and the language-class inclusion stand or fall together.","If $\\mathrm{GapP}_+\\subseteq\\mathrm{SpanP}$, then the polynomial hierarchy collapses to $\\Sigma_2^{\\mathrm{P}}$; in particular, the inclusion $\\#\\mathrm{P}\\subseteq\\mathrm{GapP}_+$ cannot be proper without such a collapse.","Any machine that computes with a $\\#\\mathrm{P}$ oracle, or with a $\\mathrm{GapP}$ oracle, can be replaced by one that makes at most one oracle query and preserves the number of accepting paths."],"supporting_citations":[{"why":"Provides Proposition 2.4, the proof source for the identities $\\mathrm{NPSV}_t=\\mathrm{FP}^{\\mathrm{NP}\\cap\\mathrm{coNP}}$ and $\\mathrm{UPSV}_t=\\mathrm{FP}^{\\mathrm{UP}\\cap\\mathrm{coUP}}$, on which the low-function characterizations depend.","marker":"[4]"},{"why":"States $\\mathrm{NPSV}_t=\\mathrm{FP}^{\\mathrm{NP}\\cap\\mathrm{coNP}}$, used to equate $\\mathrm{Low}_f(\\mathrm{SpanP})$ with $\\mathrm{NPSV}_t$ and to prove the SpanP closure theorem.","marker":"[25]"},{"why":"States $\\mathrm{UPSV}_t=\\mathrm{FP}^{\\mathrm{UP}\\cap\\mathrm{coUP}}$, used to equate $\\mathrm{Low}_f(\\#\\mathrm{P})$ with $\\mathrm{UPSV}_t$ and to connect $\\#\\mathrm{P}=\\mathrm{UPSV}_t$ with $\\mathrm{PP}=\\mathrm{UP}$.","marker":"[10]"},{"why":"Supplies the fact that every polynomial-bounded TotP function is in $\\mathrm{FP}$, used to prove $\\mathrm{Low}(\\mathrm{TotP})=\\mathrm{P}$ and several inclusion characterizations.","marker":"[2]"},{"why":"Gives the prior low-language characterizations $\\mathrm{Low}(\\#\\mathrm{P})=\\mathrm{UP}\\cap\\mathrm{coUP}$ and $\\mathrm{Low}(\\mathrm{SpanP})=\\mathrm{NP}\\cap\\mathrm{coNP}$ that the new function-level results refine.","marker":"[30]"},{"why":"Gives the GapP/SPP lowness and closure theorems that anchor the GapP rows of Table 1 and Theorem 5.3.","marker":"[6]"},{"why":"Provides earlier equivalences of $\\mathrm{FP}_+$-closure with $\\mathrm{PP}=\\mathrm{UP}$ and $\\mathrm{PP}=\\mathrm{NP}$; the paper sharpens them to $\\mathrm{UPSV}_t$ and $\\mathrm{NPSV}_t$.","marker":"[23]"},{"why":"Extends the SpanP closure equivalence to $\\mathrm{PP}=\\mathrm{NP}$, the form recovered here via $\\mathrm{NPSV}_t$.","marker":"[33]"},{"why":"Supplies the equivalent closure and collapse conditions for TotP used in Theorem 5.5 and Table 1.","marker":"[14]"},{"why":"Provides the $\\mathrm{SpanP}=\\#\\mathrm{P}$ iff $\\mathrm{NP}=\\mathrm{UP}$ characterization and the single-query oracle technique adapted in Section 6.","marker":"[17]"}],"fun_headline_variants":["Low(TotP)=P; low functions for #P and SpanP are exact","Counting functions low for #P: UPSV_t; for SpanP: NPSV_t","Closure under FP+ collapses counting classes to their low functions","Lowness for counting classes: TotP=P, #P=UPSV_t, SpanP=NPSV_t"],"cache_read_input_tokens":11520,"weakest_assumption_plain":"The main equalities rest on earlier theorems saying exactly which total single-valued functions can be computed with an oracle for a language in $\\mathrm{UP}\\cap\\mathrm{coUP}$ or $\\mathrm{NP}\\cap\\mathrm{coNP}$, and on the claim that every polynomial-bounded TotP function lies in $\\mathrm{FP}$; if either of these fails for total functions with polynomially bounded output, the characterizations of $\\mathrm{Low}_f(\\#\\mathrm{P})$, $\\mathrm{Low}_f(\\mathrm{SpanP})$, and $\\mathrm{Low}(\\mathrm{TotP})$ do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Low(TotP)=P; low functions for #P and SpanP are exact","Counting functions low for #P: UPSV_t; for SpanP: NPSV_t","Closure under FP+ collapses counting classes to their low functions","Lowness for counting classes: TotP=P, #P=UPSV_t, SpanP=NPSV_t"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000741,"raw_usage":{"total_tokens":3449,"prompt_tokens":1232,"completion_tokens":2217,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":848,"completion_tokens_details":{"reasoning_tokens":2122}},"tokens_in":848,"tokens_out":2217,"duration_ms":17884,"temperature":1.0,"reasoning_tokens":2122,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:58:12.220466+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One concrete test: look for a total function $f$ with polynomial-bounded output that lies in $\\mathrm{UPSV}_t$ but not in $\\mathrm{FP}^{\\mathrm{UP}\\cap\\mathrm{coUP}}$; if such a function exists, $\\mathrm{Low}_f(\\#\\mathrm{P})=\\mathrm{UPSV}_t$ fails. Alternatively, a language $L\\notin\\mathrm{P}$ with $\\mathrm{TotP}^L=\\mathrm{TotP}$ would refute $\\mathrm{Low}(\\mathrm{TotP})=\\mathrm{P}$.","supporting_citations":[{"cited_title":"Journal of Computer and System Sciences30(3), 395–413 (1985)","cited_arxiv_id":null,"evidence_quote":"Provides Proposition 2.4, the proof source for the identities $\\mathrm{NPSV}_t=\\mathrm{FP}^{\\mathrm{NP}\\cap\\mathrm{coNP}}$ and $\\mathrm{UPSV}_t=\\mathrm{FP}^{\\mathrm{UP}\\cap\\mathrm{coUP}}$, on which the low-function characterizations depend."},{"cited_title":"Journal of Computer and System Sciences48(2), 357–381 (1994)","cited_arxiv_id":null,"evidence_quote":"States $\\mathrm{NPSV}_t=\\mathrm{FP}^{\\mathrm{NP}\\cap\\mathrm{coNP}}$, used to equate $\\mathrm{Low}_f(\\mathrm{SpanP})$ with $\\mathrm{NPSV}_t$ and to prove the SpanP closure theorem."},{"cited_title":"SIAM Journal on Computing36(5), 1264–1300 (2006)","cited_arxiv_id":null,"evidence_quote":"States $\\mathrm{UPSV}_t=\\mathrm{FP}^{\\mathrm{UP}\\cap\\mathrm{coUP}}$, used to equate $\\mathrm{Low}_f(\\#\\mathrm{P})$ with $\\mathrm{UPSV}_t$ and to connect $\\#\\mathrm{P}=\\mathrm{UPSV}_t$ with $\\mathrm{PP}=\\mathrm{UP}$."},{"cited_title":"In: Annual Confer- ence on Theory and Applications of Models of Computation","cited_arxiv_id":null,"evidence_quote":"Supplies the fact that every polynomial-bounded TotP function is in $\\mathrm{FP}$, used to prove $\\mathrm{Low}(\\mathrm{TotP})=\\mathrm{P}$ and several inclusion characterizations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the prior low-language characterizations $\\mathrm{Low}(\\#\\mathrm{P})=\\mathrm{UP}\\cap\\mathrm{coUP}$ and $\\mathrm{Low}(\\mathrm{SpanP})=\\mathrm{NP}\\cap\\mathrm{coNP}$ that the new function-level results refine."},{"cited_title":"Journal of Computer and System Sciences48(1), 116–148 (1994)","cited_arxiv_id":null,"evidence_quote":"Gives the GapP/SPP lowness and closure theorems that anchor the GapP rows of Table 1 and Theorem 5.3."},{"cited_title":"Journal of Computer and System Sciences46(3), 295–325 (1993)","cited_arxiv_id":null,"evidence_quote":"Provides earlier equivalences of $\\mathrm{FP}_+$-closure with $\\mathrm{PP}=\\mathrm{UP}$ and $\\mathrm{PP}=\\mathrm{NP}$; the paper sharpens them to $\\mathrm{UPSV}_t$ and $\\mathrm{NPSV}_t$."},{"cited_title":"Univ., Inst","cited_arxiv_id":null,"evidence_quote":"Extends the SpanP closure equivalence to $\\mathrm{PP}=\\mathrm{NP}$, the form recovered here via $\\mathrm{NPSV}_t$."},{"cited_title":"Closure Properties and Characterizations of TotP","cited_arxiv_id":"2504.20262","evidence_quote":"Supplies the equivalent closure and collapse conditions for TotP used in Theorem 5.5 and Table 1."},{"cited_title":"Acta Infor- matica26(4), 363–379 (1989)","cited_arxiv_id":null,"evidence_quote":"Provides the $\\mathrm{SpanP}=\\#\\mathrm{P}$ iff $\\mathrm{NP}=\\mathrm{UP}$ characterization and the single-query oracle technique adapted in Section 6."}],"review_version":1}