{"id":"1f597cab-4dcb-442c-85a8-58da21722111","arxiv_id":"2608.05431","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Discrete ODE schemas over the F AC0 base algebra ACDL are claimed to characterize PH, the counting hierarchy, FModmP/⊕P, FPSPACE, and FP, with hierarchy levels given by nesting depth.","lead":"This paper proposes a unified framework in which discrete differential equations define a wide range of complexity classes, from constant-depth circuits up to polynomial space, by varying how equations are nested. It gives a map of characterizations for PH, the counting hierarchy, and ⊕P, backed by proof sketches rather than a completed formal development.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Completeness proofs rely on an unproved exponential padding function in ACDL; without it the ODE simulations cannot be instantiated at the required bound.","rationale":"The reader's weakest assumption identifies exactly the missing padding function, and my reading agrees that this is the most load-bearing gap. The central claim requires all completeness simulations to instantiate ODEs at a bound whose binary length is a polynomial function of the input length; the paper provides proof sketches but no explicit definability result for this padding in ACDL. This is a single concern that affects NP, coNP, the full polynomial hierarchy, and the modulo-counting classes, rather than a local typo. I do not move the verdict because the paper is explicitly an ongoing research report and the concern is a concrete condition that could be met by adding a lemma or by clarifying that F AC0 is non-uniform, in which case the padding function is automatically present. The FPSPACE proof also contains an arity error in the k-BR simulation, but that is isolated to one theorem and looks fixable; the padding issue is the more systemic risk to the central characterization claim.","tokens_in":70,"tokens_out":35990,"duration_ms":940853,"concrete_test":"Take r(n)=n^2+1 and attempt to construct an explicit ACDL term for x ↦ 2^{r(ℓ(x))}-1 from the basis in Remark 1 using only composition and ℓ-ODE1. If no such term exists and no separate lemma supplies it, then the inclusion NP ⊆ [ACDL; ◦0, ODE∨] in Theorem 2 fails for machines with quadratic run-time bounds. Alternatively, check the definition of F AC0 in [1]: if it is non-uniform AC0, the padding function is trivially in ACDL and the concern is resolved; if it is uniform, the construction must be exhibited.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The completeness directions, starting with Theorem 2 and propagating to Theorems 5 and 7, evaluate an ODE-defined function at the specially constructed argument 1^{r(ℓ(x))} (i.e., the number 2^{r(ℓ(x))}-1), whose binary length is the run-time bound r(ℓ(x)) of the simulated machine. The proof of Theorem 2 says 'Since V(z,x)=0 for any word z of size smaller than r(ℓ(x)), f(1#r(ℓ(x)),x)=1 iff there is a word z of size r(ℓ(x))'. This is only valid if the first argument of f is at least 2^{r(ℓ(x))}-1 so that the existential search ranges over all words of that length. The paper does not show that x ↦ 2^{r(ℓ(x))}-1 is definable in ACDL, nor does it cite a lemma to that effect. ACDL's basic functions listed in Remark 1 are 0, 1, ℓ, sg, +, -, ÷2, #, and projections, closed under composition and ℓ-ODE1; it is not immediate that this algebra can build a string of r(ℓ(x)) ones for a general polynomial r. If ACDL means non-uniform AC0, such length-only functions are trivially present, but the paper never states this uniformity convention. If ACDL is interpreted uniformly, constructing 2^{r(ℓ(x))}-1 for degree-2 polynomials already requires an iterated doubling or a smash-like capability that is not proved. This missing padding lemma is load-bearing because every completeness proof for NP, coNP, PH, and modulo-counting classes uses the same pattern: define an ODE from an ACDL verifier and then plug in an exponentially large bound. Without that bound, the ODE only searches over a polynomial range and cannot range over all computation paths.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":15496,"tokens_out":18008,"duration_ms":174650,"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":[{"comment":"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.","section":"§4 / Theorem 2 and §D / Theorem 6"},{"comment":"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.","section":"§C / Theorem 5"},{"comment":"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.","section":"§F / Theorem 9, displayed equation for fbr"}],"minor_comments":[{"comment":"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.","section":"§4 / Theorems 2 and 4"},{"comment":"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}.","section":"§B / Proposition 1(3)"},{"comment":"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.","section":"§E / Definition 8"},{"comment":"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.","section":"§F / Theorem 9"},{"comment":"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.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is honestly labeled as an ongoing research report, and many of the issues I raise are gaps in proof sketches rather than evidence against the program. I would encourage the authors to turn at least Theorems 2, 5, and 9 into full proofs, or to clearly state which results are conjectural; in its current form the paper is not yet a complete journal submission. I did not find problems with citation practices."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe paper is a high-level progress report on using discrete ODE schemas over a small function algebra (ACDL) to characterize counting and alternating complexity classes. The core idea is genuinely nice: the same algebra that captures F AC0 can, when closed under different linear ODE schemas, capture bounded search, counting, and modulo counting. The base-level results (NP, coNP, #P, FModmP) are plausible and come with explicit proof sketches, and the appendix gives a self-contained proof that accepting computation paths are checkable in F AC0. That is real content.\n\nWhat is new: the claim that ⊕P has a recursion-theoretic characterization via an ODE schema is, to my knowledge, new and worth attention. The uniform view of hierarchy levels as nesting depth of ODE operators is a useful perspective, even if it builds on earlier recursion-theoretic work of Oitavem, Wagner, and Dal Lago et al.\n\nThe soft spots are real. Most importantly, every completeness proof (starting with Theorem 2) evaluates the ODE at an argument 1^{r(ℓ(x))} — a string of ones of length equal to the machine's run time bound. The paper never shows that this exponential-length padding function is definable in ACDL. It probably is, since ACDL = F AC0 and the function is trivial for F AC0, but that must be stated and justified. Without it, the simulations only search over polynomially bounded ranges, not exponential ones. This is a load-bearing gap.\n\nThe FPSPACE proof (Theorem 9) contains a displayed formula for simulating k-bounded recursion that writes h(i,y) where h should also receive the recursion step x. As written, the arity is wrong, and the formula cannot be right. This is likely fixable, but it needs correcting. The PH and FCH hierarchy theorems are induction sketches relying on earlier work; acceptable in a report, but not complete proofs.\n\nThe paper is honest about being work in progress, and the overall framework looks promising. I would not treat the characterizations as proven yet, but the direction is solid and the base cases are credible. I would send it to peer review, with the expectation of major revision — the referees should focus on the padding lemma and the FPSPACE arity error. A reader working in implicit complexity will get a clear view of a lively research program and some concrete open questions. I would probably cite it as related work, but not as a proven characterization.","headline":"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.","tokens_in":16131,"tokens_out":7047,"would_cite":true,"duration_ms":59617,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03D15","68Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["discrete ordinary differential equations","implicit computational complexity","function algebras","polynomial hierarchy","counting hierarchy","FAC0","modular counting","PSPACE"],"falsifier":"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.","tokens_in":14906,"feed_emoji":"🧮","tokens_out":11685,"duration_ms":98680,"temperature":0.7,"pith_summary":"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.","feed_headline":"Same ODE schemas capture PH, #P, and PSPACE","feed_subtitle":"A single FAC0 base plus three linear ODE schemas reproduces PH, the counting hierarchy, and PSPACE.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes that the base algebra ACDL characterizes exactly FAC0 and supplies the ℓ-ODE1 schema used throughout.","marker":"[1]"},{"why":"Introduces discrete λ-ODE and linear length-ODE schemas and the first FP characterization, which is the starting point of the framework.","marker":"[10]"},{"why":"Provides the restricted-composition scheme and the induction over hierarchy levels used in the PH characterization.","marker":"[32]"},{"why":"Defines the counting hierarchy and supplies closure of counting classes under summation and recursion.","marker":"[36]"},{"why":"Gives closure of counting classes under restricted composition and the counting-hierarchy levels used in Theorem 6.","marker":"[19]"},{"why":"Shows that acceptance predicates for NTMs are in FAC0, the recognition step used in every completeness proof.","marker":"[35]"},{"why":"Supplies the FCRN characterization of FP used to prove Theorem 11.","marker":"[26]"},{"why":"Supplies the PSPACE characterization via CRN and k-bounded recursion used in Theorem 9.","marker":"[15]"},{"why":"Defines concatenation recursion on notation, which the ℓ-ODE1 schema simulates in the FPSPACE proof.","marker":"[16]"}],"fun_headline_variants":["Three ODE schemas rebuild PH, #P, and PSPACE","Discrete ODEs unify counting and alternating hierarchies","One algebra, three schemas: PH, #P, PSPACE","From FAC^0 to PSPACE with three ODE rules","Three linear ODE schemas reproduce PH, CH, PSPACE"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Three ODE schemas rebuild PH, #P, and PSPACE","Discrete ODEs unify counting and alternating hierarchies","One algebra, three schemas: PH, #P, PSPACE","From FAC^0 to PSPACE with three ODE rules","Three linear ODE schemas reproduce PH, CH, PSPACE"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000861,"raw_usage":{"total_tokens":3838,"prompt_tokens":1148,"completion_tokens":2690,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":764,"completion_tokens_details":{"reasoning_tokens":2600}},"tokens_in":764,"tokens_out":2690,"duration_ms":19102,"temperature":1.0,"reasoning_tokens":2600,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T13:14:16.857169+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Texts in Theoretical Computer Science","cited_arxiv_id":null,"evidence_quote":"Supplies the PSPACE characterization via CRN and k-bounded recursion used in Theorem 9."},{"cited_title":"A new characterization of fac 0 via discrete ordinary differential equations","cited_arxiv_id":null,"evidence_quote":"Establishes that the base algebra ACDL characterizes exactly FAC0 and supplies the ℓ-ODE1 schema used throughout."},{"cited_title":"Recursion schemes, discrete differential equations and characterization of polynomial time computations","cited_arxiv_id":null,"evidence_quote":"Introduces discrete λ-ODE and linear length-ODE schemas and the first FP characterization, which is the starting point of the framework."},{"cited_title":"The polynomial hierarchy of functions and its levels.Theoretical Computer Science, 900:25–34, 2022","cited_arxiv_id":null,"evidence_quote":"Provides the restricted-composition scheme and the induction over hierarchy levels used in the PH characterization."},{"cited_title":"beginning of the tape marker","cited_arxiv_id":null,"evidence_quote":"Defines the counting hierarchy and supplies closure of counting classes under summation and recursion."},{"cited_title":"Implicit recursion-theoretic characteri- zations of counting classes.Archive for Mathematical Logic, 61(7):1129–1144, 2022","cited_arxiv_id":null,"evidence_quote":"Gives closure of counting classes under restricted composition and the counting-hierarchy levels used in Theorem 6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows that acceptance predicates for NTMs are in FAC0, the recognition step used in every completeness proof."},{"cited_title":"Function algebraic characterizations of the polytime functions.Comput","cited_arxiv_id":null,"evidence_quote":"Supplies the FCRN characterization of FP used to prove Theorem 11."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines concatenation recursion on notation, which the ℓ-ODE1 schema simulates in the FPSPACE proof."}],"review_version":1}