Pith. sign in

REVIEW 4 major objections 5 minor 34 references

Low Sets and Closure Properties of Counting Function Classes

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Low(TotP)=P and the low functions for #P and SpanP are exactly the total single-valued function classes UPSV_t and NPSV_t.

desk verdict 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. read the letter →

arxiv 2507.04110 v5 pith:NRCGX72O submitted 2025-07-05 cs.CC

Yaroslav Ivanashev This is my paper · ORCID
classification cs.CC MSC 68Q1568Q17
keywords computationalcomplexitycountingclasseslownessclosureproperties#PGapPSpanTot
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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}$.

Watch

Extended reading notes

Core claim

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}}$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Theorem 3.3] 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.
  2. [Theorems 5.1 and 5.2] 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.
  3. [Corollary 6.4] 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.
  4. [Propositions 4.2 and 4.4] 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.
minor comments (5)
  1. [Table 1] 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.
  2. [Definition 2.7] 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.
  3. [Lemma 6.1] 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.
  4. [Corollary 6.4] 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.
  5. [General] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the central lowness and closure derivations are independent of the paper's self-citations.

full rationale

The paper's new derivation chain is self-contained in the relevant sense. Theorem 3.2(5) reduces Low(TotP)=P to the external fact that every polynomial-bounded TotP function lies in FP [2]; the low-language argument constructs a TotP^L characteristic function and uses lowness to pull it back to TotP, then applies [2] — no equation is presupposed. Theorem 3.3(1) is proved from the external identities UPSV_t=FP^{UP∩coUP} and NPSV_t=FP^{NP∩coNP} (Prop. 2.8, [4,10,25]) together with the classical Low(#P)=UP∩coUP; the pregraph argument is the standard one and does not assume Low_f(#P). Theorems 5.1 and 5.2 are direct: (2⇒1) uses the unconditional closure of UPSV_t/NPSV_t under FP_+, (1⇒3) uses Lemma 6.1 to identify one-query FP_+∘#P/SpanP with the full composition class, and (3⇒2) uses #P⊆FP^{PP} and SpanP⊆FP^{#P}; none of these steps is equivalent to its conclusion. The only self-citations are Theorem 2.4(1) and Theorem 5.5, both credited to the author's preprint [14]; Theorem 5.5 is stated without proof, which is an omitted-proof presentation gap, but it is not used to derive the new lowness or #P/SpanP closure theorems, so it is not load-bearing circularity. No fitted parameter is renamed a prediction, and no known result is merely relabeled.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper's central claims depend on standard counting complexity results taken from prior literature rather than on fitted parameters or invented entities. No free parameters or new primitives are introduced.

assumptions (6)
  • domain assumption Low(#P)=UP∩coUP, Low(GapP)=SPP, Low(SpanP)=NP∩coNP
    Used in Theorem 3.3 to move from a function f being low to pregraph(f) being low; cited to [30,21,6].
  • domain assumption UPSV_t=FP^{UP∩coUP} and NPSV_t=FP^{NP∩coNP}
    Proposition 2.8; used in Theorems 3.3, 4.1-4.4, and 5.1-5.2 to convert function classes to oracle classes.
  • domain assumption Every polynomial-bounded TotP function is in FP
    Used in Theorem 3.2(5) and Propositions 4.1-4.2; cited to [2].
  • standard math Toda's theorem: PH⊆P^{#P}
    Used in Theorem 2.4(4) to derive PH=Σ2^P from C=P=coNP.
  • domain assumption SpanP⊆FP^{#P[1]} (Toda-Watanabe)
    Used in Proposition 2.6 and Corollary 6.4; cited to [29,15].
  • domain assumption Oracle functions have polynomially bounded output length
    Stated before Theorem 3.3; required for oracle access to function values.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Low Sets and Closure Properties of Counting Function Classes." pith.science (2026). https://pith.science/paper/NRCGX72O

@misc{pith2026250704110,
  author       = {Pith},
  title        = {Pith review of: Low Sets and Closure Properties of Counting Function Classes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NRCGX72O}},
  note         = {Machine review of arXiv:2507.04110}
}
abstract

A language L is low for a relativizable complexity class C, if C$^{\text{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$_{\text{f}}$(#P) = UPSV$_{\text{t}}$ and Low$_{\text{f}}$(SpanP) = NPSV$_{\text{t}}$. We establish the inclusion relations between NPSV$_{\text{t}}$, UPSV$_{\text{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 = $\Sigma_{2}^{\text{P}}$. For the class #P we prove that its closure under left composition with FP$_+$ is equivalent to #P = UPSV$_{\text{t}}$, and for SpanP this closure is equivalent to SpanP = NPSV$_{\text{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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [14]

    Closure Properties and Characterizations of TotP

    Ivanashev, Y.: Closure properties and characterizations of TotP. arXiv preprint arXiv:2504.20262 (2025)

    work page Pith review arXiv 2025

  2. [1]

    Àlvarez,C.,Jenner,B.:Averyhardlog-spacecountingclass.TheoreticalComputer Science107(1), 3–30 (1993)

    work page 1993

  3. [2]

    In: Annual Confer- ence on Theory and Applications of Models of Computation

    Bakali, E., Chalki, A., Kanellopoulos, S., Pagourtzis, A., Zachos, S.: On the power of counting the total number of computation paths of NPTMs. In: Annual Confer- ence on Theory and Applications of Models of Computation. pp. 209–220. Springer (2024)

    work page 2024

  4. [3]

    SIAM Journal on Computing13(3), 461–487 (1984)

    Book, R.V., Long, T.J., Selman, A.L.: Quantitative relativizations of complexity classes. SIAM Journal on Computing13(3), 461–487 (1984)

    work page 1984

  5. [4]

    Journal of Computer and System Sciences30(3), 395–413 (1985)

    Book, R.V., Long, T.J., Selman, A.L.: Qualitative relativizations of complexity classes. Journal of Computer and System Sciences30(3), 395–413 (1985)

    work page 1985

  6. [5]

    In: Logic, automata, and computational complexity: The works of Stephen A

    Cook, S.A.: The complexity of theorem-proving procedures. In: Logic, automata, and computational complexity: The works of Stephen A. Cook, pp. 143–152 (2023)

    work page 2023

  7. [6]

    Journal of Computer and System Sciences48(1), 116–148 (1994)

    Fenner, S.A., Fortnow, L.J., Kurtz, S.A.: Gap-definable counting classes. Journal of Computer and System Sciences48(1), 116–148 (1994)

    work page 1994

  8. [7]

    In: Hemaspaandra, L., Selman, A

    Fortnow, L.: Counting complexity. In: Hemaspaandra, L., Selman, A. (eds.) Com- plexity Theory Retrospective II, pp. 81–107 (1997)

    work page 1997

Show all 34 references
  1. [8]

    SIAM Journal on Computing6(4), 675–695 (1977)

    Gill, J.: Computational complexity of probabilistic turing machines. SIAM Journal on Computing6(4), 675–695 (1977)

    1977

  2. [9]

    In: 1991 Proceedings of the Sixth Annual Structure in Complexity Theory Conference

    Gupta, S.: The power of witness reduction. In: 1991 Proceedings of the Sixth Annual Structure in Complexity Theory Conference. pp. 43–44. IEEE Computer Society (1991)

    1991

  3. [10]

    SIAM Journal on Computing36(5), 1264–1300 (2006)

    Hemaspaandra, L.A., Homan, C.M., Kosub, S., Wagner, K.W.: The complexity of computing the size of an interval. SIAM Journal on Computing36(5), 1264–1300 (2006)

    2006

  4. [11]

    ACM SIGACT News26(1), 2–13 (1995)

    Hemaspaandra, L.A., Vollmer, H.: The satanic notations: counting classes beyond #P and other definitional adventures. ACM SIGACT News26(1), 2–13 (1995)

    1995

  5. [12]

    International Journal of Foundations of Computer Science11(02), 315–342 (2000)

    Hempel, H., Wechsung, G.: The operators min and max on the polynomial hier- archy. International Journal of Foundations of Computer Science11(02), 315–342 (2000)

    2000

  6. [13]

    Ikenmeyer, C., Pak, I.: What is in #P and what is not? In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). pp. 860–871. IEEE (2022) Low Sets and Closure Properties of Counting Function Classes 11

    2022

  7. [15]

    In: Advances in Informatics: 8th Panhellenic Conference on Informatics, PCI 2001 Nicosia, Cyprus, November 8–10, 2001 Revised Selected Papers 8

    Kiayias, A., Pagourtzis, A., Sharma, K., Zachos, S.: Acceptor-definable counting classes. In: Advances in Informatics: 8th Panhellenic Conference on Informatics, PCI 2001 Nicosia, Cyprus, November 8–10, 2001 Revised Selected Papers 8. pp. 453–463. Springer (2003)

    2003

  8. [16]

    Information Processing Letters14(1), 39–43 (1982)

    Ko, K.I.: Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters14(1), 39–43 (1982)

    1982

  9. [17]

    Acta Infor- matica26(4), 363–379 (1989)

    Köbler, J., Schöning, U., Torán, J.: On counting and approximation. Acta Infor- matica26(4), 363–379 (1989)

    1989

  10. [18]

    Birkhäuser Boston, MA (1993)

    Köbler, J., Schöning, U., Torán, J.: The graph isomorphism problem: its structural complexity. Birkhäuser Boston, MA (1993)

    1993

  11. [19]

    Information Processing Letters 72(5-6), 197–203 (1999)

    Kosub, S.: A note on unambiguous function classes. Information Processing Letters 72(5-6), 197–203 (1999)

    1999

  12. [20]

    Levin, L.: Universal sorting problems. Probl. Inform. Trammiss9, 265–266 (1973)

    1973

  13. [21]

    Li, L.: On the counting functions. Ph.D. thesis, The University of Chicago (1993)

    1993

  14. [22]

    Infor- mation Processing Letters51(1), 7–10 (1994)

    Mahajan, M., Thierauf, T., Vinodchandran, N.: A note on SpanP functions. Infor- mation Processing Letters51(1), 7–10 (1994)

    1994

  15. [23]

    Journal of Computer and System Sciences46(3), 295–325 (1993)

    Ogiwara, M., Hemachandra, L.A.: A complexity theory for feasible closure prop- erties. Journal of Computer and System Sciences46(3), 295–325 (1993)

    1993

  16. [24]

    Journal of Computer and System Sciences27(1), 14–28 (1983)

    Schöning, U.: A low and a high hierarchy within NP. Journal of Computer and System Sciences27(1), 14–28 (1983)

    1983

  17. [25]

    Journal of Computer and System Sciences48(2), 357–381 (1994)

    Selman, A.L.: A taxonomy of complexity classes of functions. Journal of Computer and System Sciences48(2), 357–381 (1994)

    1994

  18. [26]

    PhD thesis, Cornell University, Ithaca (1975)

    Simon, J.: On some central problems in computational complexity. PhD thesis, Cornell University, Ithaca (1975)

    1975

  19. [27]

    computa- tional complexity4, 242–261 (1994)

    Thierauf, T., Toda, S., Watanabe, O.: On closure properties of GapP. computa- tional complexity4, 242–261 (1994)

    1994

  20. [28]

    SIAM Journal on Com- puting20(5), 865–877 (1991)

    Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM Journal on Com- puting20(5), 865–877 (1991)

    1991

  21. [29]

    Theoretical Computer Science100(1), 205–221 (1992)

    Toda, S., Watanabe, O.: Polynomial-time 1-Turing reductions from #PH to #P. Theoretical Computer Science100(1), 205–221 (1992)

    1992

  22. [30]

    Torán Romero, J.: Structural properties of the counting hierarchies. Ph.D. thesis (1988)

    1988

  23. [31]

    Information pro- cessing letters5(1), 20–23 (1976)

    Valiant, L.G.: Relative complexity of checking and evaluating. Information pro- cessing letters5(1), 20–23 (1976)

    1976

  24. [32]

    Theoretical computer science8(2), 189–201 (1979)

    Valiant, L.G.: The complexity of computing the permanent. Theoretical computer science8(2), 189–201 (1979)

    1979

  25. [33]

    Univ., Inst

    Vollmer, H., Wagner, K.W.: Classes of counting functions and complexity theoretic operators. Univ., Inst. für Informatik (1996)

    1996

  26. [34]

    Acta informatica23, 325–356 (1986)

    Wagner, K.W.: The complexity of combinatorial problems with succinct input representation. Acta informatica23, 325–356 (1986)

    1986

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.