Pith. sign in

REVIEW 3 major objections 5 minor 39 references

Towards a Characterization of Counting and Alternating Classes via Discrete Ordinary Differential Equations

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

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

Pith's one-line read This paper claims that the polynomial hierarchy, the counting hierarchy, FModmP, FPSPACE, and FP can all be characterized by one base algebra of F AC0 functions closed under a small family of linear discrete ODE schemas, with hierarchy…

desk verdict A promising but still rough sketch of a unified ODE-based framework for counting and alternating classes; the base cases are credible, but the hierarchy and FPSPACE proofs have gaps that need addressing before the characterizations are taken as proven. read the letter →

arxiv 2608.05431 v1 pith:F75PXO5A submitted 2026-08-05 cs.CC

Melissa Antonelli , Eduardo Skapinakis This is my paper · ORCID
classification cs.CC MSC 03D1568Q15
keywords discreteordinarydifferentialequationsimplicitcomputationalcomplexityfunctionalgebraspolynomialhierarchycountingFAC0modularPSPACE
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 argues that a single algebraic starting point—the function algebra $\mathrm{ACDL}$, which computes exactly the $\mathrm{FAC}^0$ functions—can be turned into characterizations of the polynomial hierarchy, the counting hierarchy, and several other classes by closing it under restricted composition and a small family of linear discrete ODE schemas. The key claim is that the complexity level is controlled almost entirely by the nesting depth of the ODE operator: one existential-search ODE over $\mathrm{FAC}^0$ gives $\mathrm{NP}$, adding another nest gives $\Sigma^p_2$, and so on; replacing existential search by a summing ODE gives $\#\mathrm{P}$ and the counting hierarchy. The same framework, with different linearity restrictions, is claimed to capture $\mathrm{FMod}_m\mathrm{P}$ (hence $\oplus\mathrm{P}$), $\mathrm{FPSPACE}$, and $\mathrm{FP}$. A sympathetic reader would care because this would unify machine-independent characterizations of these classes under one mechanism and connect them to descriptive complexity, where $\mathrm{FO}$/$\mathrm{AC}^0$ is the usual base.

What carries the argument

The load-bearing mechanism is the linear discrete ODE schema together with restricted composition. A $\lambda$-ODE computes $f(x+1,y) = f(x,y) + (\lambda(x+1,y)-\lambda(x,y)) \cdot u(x,y,f(x,y))$, so the number of update steps is governed by the growth of $\lambda$; taking $\lambda = \ell$ (binary length) gives logarithmic steps, while deriving along $x$ gives polynomially many steps. Linearity restrictions force the recursive call to appear only under a sign function, so the solution stays bounded and search or counting can be read off: $\mathrm{ODE}^{\lor}$ is existential bounded search ($f=1$ iff some $k=1$), $\mathrm{ODE}^{\land}$ is universal bounded search, $\mathrm{ODE}^{\#}$ is summation over $k$, and $\mathrm{ODE}^{\mathrm{cmod}\text{-}m}$ is summation modulo $m$. Restricted composition, where the inner functions of a composition must lie in the base algebra, is what keeps the levels separated, since classes like $\mathrm{NP}$ are not known to be closed under complement.

What would settle it

Check the completeness direction of Theorem 2 for a fixed polynomial run-time bound, say $r(n)=n^2$, and try to write the padding function $x \mapsto \mathbf{1}^{\# r(\ell(x))}$ as an $\mathrm{ACDL}$ term that uses no ODE schemas; if it cannot be done, the simulation does not produce a function of $x$ in the algebra and the level-one characterization fails.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is a uniform 'one algebra, many classes' theorem family. Starting from $\mathrm{ACDL} = \mathrm{FAC}^0$, the schemas $\mathrm{ODE}^{\lor}$ (existential bounded search), $\mathrm{ODE}^{\land}$ (universal bounded search), and $\mathrm{ODE}^{\#}$ (summation) are the only ingredients needed to move up the polynomial and counting hierarchies: Theorem 5 states $\mathrm{PH} \equiv \mathrm{SDL} = [\mathrm{ACDL}; \circ, \mathrm{ODE}^{\lor}]$ with $\Sigma^p_{n+1} \equiv [\mathrm{SDL}_n; \circ_0, \mathrm{ODE}^{\lor}]$, and Theorem 6 states $\mathrm{FCH} \equiv \mathrm{CDL} = [\mathrm{ACDL}; \circ, \mathrm{ODE}^{\#}]$ with $\mathrm{FCH}_{n+1} = [\mathrm{CDL}_n; \circ_0, \mathrm{ODE}^{\#}]$. Theorem 7 gives $\mathrm{FMod}_m\mathrm{P} \cup \mathrm{FAC}^0 = [\mathrm{ACDL}; \circ_0, \mathrm{ODE}^{\mathrm{cmod}\text{-}m}]$, Theorem 9 gives $\mathrm{FPSPACE} = [B; \circ, \ell\text{-}\mathrm{ODE}^1, \mathrm{bODE}]$, and Theorem 11 gives $\mathrm{FP} = [\mathrm{ACDL}; \circ, \ell\text{-}\mathrm{ODE}^1]$. The unified mechanism is that an $\mathrm{FAC}^0$ function recognizes accepting computation paths of a machine, and the ODE schemas then search over or count those paths, with linearity restrictions keeping the search or count bounded.

Load-bearing premise

The completeness proofs evaluate the ODE-defined function at the padded argument $\mathbf{1}^{\# r(\ell(x))}$, a number whose binary length is the run-time bound $r(\ell(x))$ of the simulated machine, and the paper does not prove that this padding function can be defined inside $\mathrm{ACDL}$ and supplied as an argument under the restricted composition rule.

Editorial extensions

If this is right

  • Every level $\Sigma^p_n$ and $\Pi^p_n$ would be describable as the $n$-th nesting of an existential or universal ODE over $\mathrm{FAC}^0$, giving a machine-independent account of alternation depth.
  • $\#\mathrm{P}$ and the counting hierarchy would be captured by the same base algebra with summation in place of search, so counting complexity would be presented as iterated discrete integration of $\mathrm{FAC}^0$-recognizable predicates.
  • $\oplus\mathrm{P}$ and $\mathrm{FMod}_m\mathrm{P}$ would receive recursion-theoretic and ODE characterizations for the first time, which the paper notes was previously missing.
  • $\mathrm{FPSPACE}$ would be obtained by deriving along $x$ with a bounded linearity restriction, and $\mathrm{FP}$ by a non-strict form of $\ell$-ODE$^1$; both would fall out of the same framework, making the difference between polynomial time and polynomial space a matter of which clock the ODE derives along.
  • Because the base is only $\mathrm{FAC}^0$, the characterizations would strengthen earlier recursion-theoretic treatments that start from $\mathrm{FP}$ or $\mathrm{P}$, and would align with descriptive complexity's use of $\mathrm{FO}$/$\mathrm{AC}^0$ as the ground level.

Reading between the lines

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

  • Not in the paper: if the nesting-depth picture is right, then these classes form a single two-dimensional landscape, with ODE nesting depth on one axis and the linearity or clock restriction on the other; classes like $\mathrm{LOGSPACE}$ or $\mathrm{NC}$ may have natural coordinates in that landscape.
  • Not in the paper: replacing the fixed modulus $m$ in $\mathrm{ODE}^{\mathrm{cmod}\text{-}m}$ by a threshold would yield ODE schemas for threshold counting classes such as $\mathrm{PP}$, a direction the paper only gestures at with its modular example.
  • Not in the paper: the framework suggests that standard separations, such as $\mathrm{NP} \neq \mathrm{coNP}$, could be rephrased as the non-interdefinability of the $\mathrm{ODE}^{\lor}$ and $\mathrm{ODE}^{\land}$ schemas over $\mathrm{ACDL}$, an equivalence the paper does not state.
  • Not in the paper: the paper's remark that $\mathrm{bODE}$ mirrors the $\mathrm{FNC}^1$ schema hints that deriving along $\ell$ versus along $x$ tracks circuit depth versus space; intermediate derivation rates could define intermediate circuit classes, though the paper does not develop this test.
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

3 major / 5 minor

Summary. The manuscript is a high-level research report presenting a unified implicit-complexity framework based on discrete ordinary differential equations. Starting from the function algebra ACDL, which the authors previously showed to equal F AC0, it proposes to capture NP, coNP, the levels of PH and FCH, FModmP, FPSPACE, and FP by closing ACDL under restricted composition and various linear ODE schemas. The paper contains proof sketches for the base characterizations (Theorems 2, 4, 7, 11), an induction sketch for the polynomial and counting hierarchies (Theorems 5 and 6), a sketch for FPSPACE (Theorem 9), and a full self-contained proof that accepting computation predicates are F AC0-checkable (Appendix A).

Significance. If the claimed characterizations are correct, the framework is genuinely attractive: a single base algebra much weaker than FP, together with a small family of linear ODE schemas, would uniformly explain alternation, counting, modulo counting, polynomial space, and polynomial time. The paper makes concrete, falsifiable claims and does not fit data with free parameters. It also contains a useful self-contained proof of the F AC0-checkability of accepting computations, and it explicitly builds on published prior work rather than on circular reasoning. The significance is conditional, however, because several load-bearing proofs are only sketches and at least one displayed formula appears incorrect.

major comments (3)
  1. [§4 / Theorem 2 and §D / Theorem 6] The completeness directions evaluate ODE-defined functions at the specially constructed argument 1^{r(ℓ(x))}, but the manuscript nowhere proves that the function x ↦ 2^{r(ℓ(x))} − 1 is definable in ACDL or is an admissible inner function for the restricted composition ◦0. This is load-bearing: the same pattern is reused in Theorems 4, 6, and 7, and without the ability to supply this exponentially long bound the ODE search ranges over the wrong domain. The gap is likely repairable, since ACDL = F AC0 [1] and the tally function for a fixed polynomial r appears to be F AC0-computable, but the manuscript should either prove this or cite an explicit lemma stating it.
  2. [§C / Theorem 5] The proof of the polynomial-hierarchy characterization is only an induction sketch. In the (⊇) direction the text asserts that the restricted-composition condition 'allows functions in SDLn to be freely composed' and then uses cosg to obtain Πp_n predicates, but it does not explain how existential search over functions in SDLn beyond characteristic functions is handled. In the (⊆) direction, the proof relies on the induction hypothesis that the closure of SDLn under composition is contained in FP^{Σp_n}, yet it never verifies this hypothesis for n+1 and never proves that the non-Boolean functions of SDLn stay inside FP^{Σp_n}. Since Theorem 5 is one of the central claims, the proof needs to be completed or the exact supporting lemmas from [32] and [6] need to be cited step by step.
  3. [§F / Theorem 9, displayed equation for fbr] The simulation of k-bounded recursion is incorrect as written. The displayed equation for fbr has right-hand side depending on h(i, y) and on the indicators of fbr(x, y), but k-BR, as defined in the same appendix, requires f(x+1, y) = h(x, y, f(x, y)). The proposal therefore omits the dependence on the recursion argument x and on the previous value f(x, y). This is not a mere presentation issue: the displayed formula does not define the intended k-BR function. The authors should correct the formula and then show that the corrected expression is an allowed instance of bODE.
minor comments (5)
  1. [§4 / Theorems 2 and 4] The notation 'F AC0 ∪ NP' and 'F AC0 ∪ coNP' mixes a class of functions with classes of decision problems; the intended meaning should be stated explicitly, e.g., by using the ≡ convention for characteristic functions that is introduced later in Section C.
  2. [§B / Proposition 1(3)] The final sentence says the count includes 'g(y) = 1 and t ∈ {1, . . . , x−1}', but the displayed formula sums k2(u, y) for u from 0 to x−1 in addition to g(y); the index set should be {0, . . . , x−1}.
  3. [§E / Definition 8] The ODEcmod-m schema uses the floor operation ⌊·/m⌋, which is not in the signature {+, −, ×, sg} allowed for the linear schemas in Definition 2. The paper should state explicitly that ODEcmod-m is a new primitive schema, since the soundness proof in Theorem 7 treats it as such.
  4. [§F / Theorem 9] The sentence 'Since our class contains PSPACE' should be phrased more carefully: the algebra is a class of functions, so what is meant is that it contains the characteristic functions of PSPACE.
  5. [Table 1] The table is difficult to read without a legend: the entries such as '−f×k2+k2' and 'f×A+B' mix the syntactic shape of the schema with the classes being characterized, and the rows 'lev. 1', 'lev. n', and 'union' are not explained in the caption.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's class equalities are derived from published external characterizations and explicit ODE semantics, not from fitted data or definitional collapse.

full rationale

The paper's central claims are function-algebra equalities, not empirical predictions; there are no fitted parameters and no quantity is 'predicted' after being used as an input. The main potential concern is the repeated use of the authors' earlier theorem ACDL = FAC0 ([1], also [2]-[4]). This is load-bearing in the proofs, but it is a published, parameter-free characterization used as a lemma, and the paper does not cite it to assume the target equalities themselves. The key machine-dependent ingredient, that acceptance of a computation path is an FAC0 predicate, is proved self-containedly in Appendix A (Theorem 3). The ODE schemas are given explicit semantics in Proposition 1: ODE∨ is existential bounded search, ODE∧ is universal bounded search, and ODE# is counting, so the later equalities follow by direct computation rather than by renaming. Completeness directions additionally rest on external characterizations (Clote [15] for PSPACE, Ishihara [26] for FP, Wagner [36] for the counting hierarchy) and standard closure facts, not on a self-citation chain. A genuine proof gap exists in the completeness arguments: the padding bound 1#r(ell(x)) is not proved definable inside ACDL, and without it the ODE simulation may not be instantiable as a function of x. However, that is a correctness/completeness gap, not a circular reduction: the missing helper function is not the same as the target class, and proving it would not make the derivation definitionally circular. Under the stated rules, self-citation without a reduction of the target claim to the cited claim does not raise the circularity score; the derivation has independent content.

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

The framework imports several external characterization theorems as black boxes: ACDL=F AC0 from the authors' prior work, Clote's PSPACE characterization, Ishihara's FP characterization, and closure properties from Wagner and Dal Lago et al. No free parameters are fitted to data, and no new entities such as particles, forces, or dimensions are postulated. The ODE schemas are formal definitions introduced by the paper, not independent axioms.

assumptions (6)
  • domain assumption ACDL = F AC0 (Antonelli, Durand and Kontinen [1])
    Used as the base algebra equality in Theorems 2, 4, 5, 6, 7, and 11; cited from the authors' earlier published work and not re-proven here.
  • domain assumption PSPACE is characterized by [0,ℓ,s0,s1,BIT,#,π;◦,CRN,k-BR] for k≥4 (Clote, Theorem 8 of this paper, [15,16])
    Used as the starting point for the FPSPACE characterization in Theorem 9.
  • domain assumption FP is characterized by [0,s0,s1,mod2,msp,#;◦,FCRN] (Ishihara, Theorem 10 of this paper, [26])
    Used in the proof of the FP characterization, Theorem 11.
  • domain assumption The counting hierarchy has the closure properties stated in Wagner [36] and Dal Lago, Kahle, Oitavem [19], namely closure under ODE# and restricted composition
    Used in Theorem 6 and Theorem 7 for the FCH and FModmP characterizations.
  • domain assumption PH levels are closed under bounded existential/universal search and restricted composition (Balcázar et al. [6, Th 8.8(e), Prop 8.1(f)], Oitavem [32, Prop 4])
    Used in Theorem 5 to justify the induction over hierarchy levels.
  • standard math Solutions of linear discrete ODEs have the closed forms stated in Def. 2 and Prop. 1 (standard difference calculus)
    Used throughout to interpret the ODE schemas; this is standard mathematics and not in dispute.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Towards a Characterization of Counting and Alternating Classes via Discrete Ordinary Differential Equations." pith.science (2026). https://pith.science/paper/F75PXO5A

@misc{pith2026260805431,
  author       = {Pith},
  title        = {Pith review of: Towards a Characterization of Counting and Alternating Classes via Discrete Ordinary Differential Equations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F75PXO5A}},
  note         = {Machine review of arXiv:2608.05431}
}
read the original abstract

This paper presents a high-level report on an ongoing project aiming to leverage implicit approaches based on discrete ordinary differential equations (ODEs) to study multiple complexity classes, even beyond small circuit and polynomial-time classes. Stimulated by recent ODE-based characterizations of polynomial-time functions (FP) and classes over the reals, the research project outlined here pushes this investigation further into counting and alternation. Specifically, we present a uniform framework, built upon a single base algebra and a unified family of schemas, where complexity levels, such as those of the polynomial and counting hierarchies, are captured simply by the nesting depth of ODE operators. Crucially, our approach starts from a base class much weaker than FP, thus strengthening existing recursion-theoretic treatments and establishing a natural connection to descriptive complexity. Moreover, by isolating three elementary schemas, our framework makes the computational content of linearity restrictions completely transparent while extending ODE-based implicit complexity to previously unaddressed counting classes, such as oplusP. More generally, this work establishes a clear bridge between differentiation and counting, offering a fresh perspective on the relationships between different complexity classes, which remains the object of ongoing and future research.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 38 canonical work pages

  1. [1]

    A new characterization of fac 0 via discrete ordinary differential equations

    Melissa Antonelli, Arnaud Durand, and Juha Kontinen. A new characterization of fac 0 via discrete ordinary differential equations. In Rastislav Kr´ alovic and Anton ´ ın Kucera, editors, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, Bratislava, Slovakia, August 26-30, 2024, volume 306 ofLIPIcs, pages 10:1–10:18. ...

    work page 2024

  2. [32]

    The polynomial hierarchy of functions and its levels.Theoretical Computer Science, 900:25–34, 2022

    Isabel Oitavem. The polynomial hierarchy of functions and its levels.Theoretical Computer Science, 900:25–34, 2022

    work page 2022

  3. [6]

    Springer, 1988

    Luis Balc´ azar, Josep D ´ ıaz, and Joaquim Gabarr´ o.Structural Complexity I. Springer, 1988

    work page 1988

  4. [2]

    Characterizing small circuit classes from F AC0 to F AC1 via discrete ordinary differential equations

    Melissa Antonelli, Arnaud Durand, and Juha Kontinen. Characterizing small circuit classes from F AC0 to F AC1 via discrete ordinary differential equations. In50th International Symposium on Mathematical Foundations of Computer Science, 2025

    work page 2025

  5. [3]

    Towards new characterizations of small circuit classes via discrete ordinary differential equations.Theoretical Computer Science, 1062:115655, 2026

    Melissa Antonelli, Arnaud Durand, and Juha Kontinen. Towards new characterizations of small circuit classes via discrete ordinary differential equations.Theoretical Computer Science, 1062:115655, 2026

    work page 2026

  6. [4]

    Recursion and proof theoretical characteri- zations of small circuit classes with modulo counting via discrete differential equations

    Melissa Antonelli, Arnaud Durand, and Rui Li. Recursion and proof theoretical characteri- zations of small circuit classes with modulo counting via discrete differential equations. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 2026, accepted

    work page 2026

  7. [5]

    Cambridge University Press, 2009

    Sanjeev Arora and Boaz Barak.Computational complexity: a modern approach. Cambridge University Press, 2009

    2009

  8. [7]

    A new recursion-theoretic characterization of poly-time functions.Computational Complexity, 2:97–110, 1992

    Stephen Bellantoni and Stephen Cook. A new recursion-theoretic characterization of poly-time functions.Computational Complexity, 2:97–110, 1992

    work page 1992

Show all 39 references
  1. [8]

    Monotonicity constraints in charac- terizations of pspace.Journal of Logic and Computation, 22(2):179–195, 2012

    Amir M Ben-Amram, Bruno Loff, and Isabel Oitavem. Monotonicity constraints in charac- terizations of pspace.Journal of Logic and Computation, 22(2):179–195, 2012

    2012

  2. [9]

    Manon Blanc and Olivier Bournez. A characterisation of functions computable in polynomial time and space over the reals with discrete ordinary differential equations: Simulation 6 of turing machines with analytic discrete ODEs. In J´ erˆ ome Leroux, Sylvain Lombardy, and David...

    2023

  3. [10]

    Recursion schemes, discrete differential equations and characterization of polynomial time computations

    Olivier Bournez and Arnaud Durand. Recursion schemes, discrete differential equations and characterization of polynomial time computations. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors,44th International Symposium on Mathematical Founda- tions of Comp...

    2019

  4. [11]

    Olivier Bournez, Daniel Silva Gra¸ ca, and Amaury Pouly. Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length: The general purpose analog computer and computable analysis are two efficiently equivalent models of computatio...

    2016

  5. [12]

    Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length.J

    Olivier Bournez, Daniel Silva Gra¸ ca, and Amaury Pouly. Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length.J. ACM, 64(6):38:1–38:76, 2017

    2017

  6. [13]

    Two queries.Journal of Computer and System Sciences, 59(2):182–194, 1999

    Harry Buhrman and Lance Fortnow. Two queries.Journal of Computer and System Sciences, 59(2):182–194, 1999

    1999

  7. [14]

    Buss.Bounded Arithmetic

    Samuel R. Buss.Bounded Arithmetic. PhD thesis, University of California, Berkeley, 1985

    1985

  8. [15]

    Texts in Theoretical Computer Science

    Peter Clote and Evangelos Kranakis.Boolean Functions and Computation Models. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002

    2002

  9. [16]

    Peter G. Clote. Sequential, machine-independent characterizations of the parallel complexity classes alogtime, ack, nck and nc. In S.R. Buss and P.J. Scott, editors,Progress in Computer Science and Applied Logic, Progress in Computer Science and Applied Logic, page 49–69. Birk...

    1990

  10. [17]

    Clote and Gaisi Takeuti

    Peter G. Clote and Gaisi Takeuti. Bounded arithmetic for NC, ALogTIME, L and NL. Annals of Pure and Applied Logic, 56(1):73–117, 1992

    1992

  11. [18]

    The intrinsic computational difficulty of functions

    Alan Cobham. The intrinsic computational difficulty of functions. In Y. Bar-Hillel, editor, Logic, Methodology and Philosophy of Science II, pages 24–30. North-Holland, 1965

    1965

  12. [19]

    Implicit recursion-theoretic characteri- zations of counting classes.Archive for Mathematical Logic, 61(7):1129–1144, 2022

    Ugo Dal Lago, Reinhard Kahle, and Isabel Oitavem. Implicit recursion-theoretic characteri- zations of counting classes.Archive for Mathematical Logic, 61(7):1129–1144, 2022

    2022

  13. [20]

    Generalized first-order spectra and polynomial-time recognizable sets

    Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. Complexity of computation, 7:43, 1974

    1974

  14. [21]

    Computational complexity of probabilistic Turing machines.SIAM Journal of Computing, 6(4):675–695, 1977

    John Gill. Computational complexity of probabilistic Turing machines.SIAM Journal of Computing, 6(4):675–695, 1977

    1977

  15. [22]

    Jean-Yves Girard, Andre Scedrov, and Philip J. Scott. Bounded linear logic: a modular approach to polynomial-time computability.Theoretical Computer Science, 97(1):1–66, 1992. 7

    1992

  16. [23]

    Monotone complexity

    Michelangelo Grigni and Michael Sipser. Monotone complexity. InProceedings of the London Mathematical Society Symposium on Boolean Function Complexity, pages 57–75, 1992

    1992

  17. [24]

    Expressibility and parallel complexity.SIAM Journal on Computing, 18(3):625–638, 1989

    Neil Immerman. Expressibility and parallel complexity.SIAM Journal on Computing, 18(3):625–638, 1989

    1989

  18. [25]

    Springer Science & Business Media, 2012

    Neil Immerman.Descriptive complexity. Springer Science & Business Media, 2012

    2012

  19. [26]

    Function algebraic characterizations of the polytime functions.Comput

    Hajime Ishihara. Function algebraic characterizations of the polytime functions.Comput. Complex., 8(4):346–356, 1999

    1999

  20. [27]

    A foundational delineation of poly-time.Information and Computation, 110(2):391–420, 1994

    Daniel Leivant. A foundational delineation of poly-time.Information and Computation, 110(2):391–420, 1994

    1994

  21. [28]

    Ramified recurrence and computational complexity II: substitution and poly-space

    Daniel Leivant and Jean-Yves Marion. Ramified recurrence and computational complexity II: substitution and poly-space. InInternational Workshop on Computer Science Logic, pages 486–500. Springer, 1994

    1994

  22. [29]

    A characterization of alternating log time by ramified recurrence.Theoretical Computer Science, 236(1-2):193–208, 2000

    Daniel Leivant and Jean-Yves Marion. A characterization of alternating log time by ramified recurrence.Theoretical Computer Science, 236(1-2):193–208, 2000

    2000

  23. [30]

    Characterizing PSPACE with pointers.Mathematical Logic Quarterly, 54(3):323–329, 2008

    Isabel Oitavem. Characterizing PSPACE with pointers.Mathematical Logic Quarterly, 54(3):323–329, 2008

    2008

  24. [31]

    A recursion-theoretic approach to np.Annals of Pure and Applied Logic, 162(8):661–666, 2011

    Isabel Oitavem. A recursion-theoretic approach to np.Annals of Pure and Applied Logic, 162(8):661–666, 2011

    2011

  25. [33]

    Subrecursiveness: Machine-independent notions of computability in restricted time and storage.Mathematical Systems Theory, 6(1):3–15, 1972

    David B Thompson. Subrecursiveness: Machine-independent notions of computability in restricted time and storage.Mathematical Systems Theory, 6(1):3–15, 1972

    1972

  26. [34]

    The complexity of computing the permanent.Theoretical Computer Science, 8(2):189–201, 1979

    Leslie Gabriel Valiant. The complexity of computing the permanent.Theoretical Computer Science, 8(2):189–201, 1979

    1979

  27. [35]

    Heribert Vollmer and Klaus W. Wagner. Recursion theoretic characterizations of complexity classes of counting functions.Theoretical Computer Science, 163(1):245–258, 1996

    1996

  28. [36]

    beginning of the tape marker

    Klaus W. Wagner. Some observations on the connection between counting and recursion. Theoretical Computer Science, 47:131–147, 1986. 8 A Checking accepting computations We prove that checking if a word represent an accepting computation can be done in F AC0. This result has be...

    1986

  29. [37]

    ODE∧ from g(y) := 1and k1(x, y) := k(x, y) − 1(with k taking values in {0, 1}), then f(x,y) = 1iff for everyi≤x−1,k(i,y) = 1

  30. [38]

    ODE∨ from g(x, y) := 0and k2(x, y) = k(x, y), then f (x, y) = 1iff there is i≤x− 1 s.t.k 2(i,y) = 1

  31. [39]

    ODE # fromg(x,y) := 0andk 2(x,y) =k(x,y), thenf(x,y) = Px−1 u=0 k2(u,y). Proof. The proof follows by Def. 2 and solutions of linear systems. Regarding item 1, it is easy to see that a function defined by ODE ∧ from g(y) = 1 and k1(x, y) = k(x, y) − 1 performs the following com...

Pith tools

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