Pith. sign in

REVIEW 3 major objections 4 minor 16 references

Pointers in Recursion: Exploring the Tropics

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · 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 a pointer-recursion framework, constrained by a new tropical tiering of only four tiers, characterizes logspace, logspace/polylogtime, P, and NC without explicit resource bounds.

desk verdict A genuinely new pointer-recursion framework with a crisp tiering discipline; the claimed logspace/P/NC characterizations are plausible but rest on a sketched simulation whose load-bearing 'simple bricks' are not exhibited. read the letter →

arxiv 1908.04922 v1 pith:O5OQ2PH5 submitted 2019-08-14 cs.CC cs.LOcs.PL

Paulin Jacobé de Naurois (CNRS/université paris13) This is my paper · ORCID
classification cs.CCcs.LOcs.PL MSC 03D2068Q15
keywords pointerrecursiontropicaltieringfunctionalgebraslogspacepolylogtimeNCrandomaccessTuringmachineonnotations
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 aims to give one recursion-theoretic platform on which several sub-polynomial complexity classes emerge from syntax alone, with no explicit time or space bounds. It replaces direct access to the input by two pointer constructs, Read and Offset, which mimic the random-access Turing machine and make unit-cost input access part of the recursion calculus. The new device is tropical tiering: four tiers ($1,0,-1,-\infty$) that force a non-size-increasing behavior via a tropical polynomial interpretation. With standard recursion schemes, the paper proves that tropical-tiered pointer recursion equals logspace (with logarithmic output), logspace/polylogtime, P, and NC. A sympathetic reader would care because it unifies known characterizations under one minimal basic-function set and one data structure.

What carries the argument

The load-bearing mechanism is tropical tiering, a syntactic assignment of each argument to one of four tiers ($1$, $0$, $-1$, $-\infty$), written with the separator `≀`. Composition and recursion are allowed only in patterns that keep output size under the tropical polynomial bound $|f(x_1,\dots,x_n)| \le \max_t\{T_t(f)+|x_t|, c_f\}$; this bound is the non-size-increasing engine that forces every intermediate string to stay logarithmic in the input length. Mutual recursion of fixed width supplies the constant $k$ in a $k\log n$ space bound without multiplicative constants, and the Read/Offset constructs supply unit-cost access to the actual input, the analogue of a random-access Turing machine's pointer tape.

What would settle it

Write out a complete L-tropical definition of the in-place one-bit replacement used in the transition-map simulation (Section 4.3) and inspect the tropical tiers: if any required subfunction needs recursion on values or a tier outside $\{1,0,-1,-\infty\}$, the logspace lower bound fails. A smaller test of the same kind is to define 'scan to the first 1 and output its prefix' entirely within the L-tropical rules and verify that all intermediate strings satisfy Proposition 4.1's size bound.

Watch

Extended reading notes

Core claim

The central claim is that the usual partial and primitive recursive functions survive translation into a pointer-recursion framework, and that complexity classes appear by choosing a tiering discipline on the pointers. With safe/normal tiering, pointer recursion is exactly polylogtime computation. With the new tropical tiering, the L-tropical functions are exactly the functions computable in logarithmic space with logarithmic-size output (Theorem 4.4); dropping recursion on values gives logspace/polylogtime (Theorem 5.2); adding substitutions gives P (Theorem 6.2); and restricting substitutions to recursion on notations gives NC (Theorem 6.4). The logspace direction works by simulating a logspace random-access Turing machine: a configuration is encoded as $2k+3$ binary strings of length $\lceil\log(n+1)\rceil$, the transition map is built from 'simple bricks' such as scanning and in-place one-bit replacement, and nested tropical recursion iterates the map the required number of steps.

Load-bearing premise

The inclusion logspace ⊆ L-tropical in Theorem 4.4 depends on the 'simple bricks'—boolean encoding and connectives, scanning for a 1-bit, left/right substring extraction, and in-place one-bit replacement—being definable with the four allowed tiers ($1,0,-1,-\infty$) and without recursion on values; the proof asserts this definability but does not display the constructions.

Editorial extensions

If this is right

  • Every function computable in logarithmic space with logarithmic output can be written as an L-tropical function over the small base set hd, tl, s0, s1, s, Read, Offset, and projections, with no resource bound written into the syntax.
  • The same four-tier syntax, with substitutions added or removed, also delivers P and NC, so one framework reproduces the main hierarchy below and at P without changing the data structure.
  • The tropical interpretation turns the space bound into a size bound: any function accepted by the tiering is automatically non-size-increasing, making the logspace upper bound a corollary of a polynomial interpretation rather than of an explicit space counter.
  • Because safe/normal tiering in the same pointer framework already gives polylogtime, the comparison shows exactly where the extra power of logspace comes from: recursion on values over logarithmically sized pointers, not from a larger basic function set.
  • The equivalence between pointer recursion and the classical partial and primitive recursive functions (Theorem 2.1) shows that the new Read/Offset constructs change the resource behavior of the calculus without changing its extensional power.

Reading between the lines

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

  • An implicit consequence is that the Read/Offset split suggests a dual Write construct in the same syntax could make function classes with polynomially long outputs first-class, without leaving the framework; the paper mentions this possibility but does not formalize it.
  • A natural test of the method's granularity is to add a recursion-rank index to tropical functions and ask whether rank $i$ functions land inside each NC$_i$; the paper raises this question for future work, and the four-tier syntax seems fine-grained enough to attempt it.
  • The tropical polynomial interpretation is in principle a quantitative tool: one could vary the allowed tier set (for example, dropping the $-1$ tier entirely) and see which sub-logspace or one-way classes the smaller discipline captures, a boundary the paper does not explore.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper introduces a pointer recursion framework in which functions receive only an offset encoding the length of the computation input and access actual input bits through a unit-cost Read construct. It claims that classical primitive and recursive functions are recovered (Theorem 2.1), that pointer safe recursion characterizes polylogtime (Theorem 3.1), and that a new four-tier "tropical" tiering discipline yields exact characterizations of logspace with logarithmic-size output (Theorem 4.4), logspace/polylogtime (Theorem 5.2), P (Theorem 6.2), and NC (Theorem 6.4). The tiering rules are syntactic, in the style of Bellantoni and Cook, and Proposition 4.1 provides a tropical polynomial interpretation that bounds output sizes linearly in the input sizes.

Significance. If the main theorems are correct, this is a valuable contribution: it offers a uniform, syntax-only framework for several sub-polynomial complexity classes, with a non-size-increasing tiering discipline expressed directly in the syntax using only four tier values. The upper-bound direction is credible and conceptually clean: Proposition 4.1 and Corollary 4.2 give a concrete argument that tropically tiered functions are computable in logspace. The paper is also honest about its open points, such as the possible refinement to NC_i in Section 7. However, the lower-bound simulations are asserted at a schematic level rather than constructed, and the missing details are load-bearing for the paper's central characterizations. No machine-checked proofs or code accompany the manuscript.

major comments (3)
  1. [Section 4.2, proof of Proposition 4.1] The proof of the logspace lower bound reduces the simulation of a random-access Turing machine to four "simple bricks" (boolean functions, scanning, substring extraction, and one-bit replacement) and to a transition map Next of width 2k+3, but none of these is actually constructed. In particular, one-bit replacement at a position given by a prefix requires, during the linear scan, an equality test between the current prefix and the target position; this is not a basic function, and the paper does not show that such a comparison is definable in the four-tier discipline without recursion on values. Since Theorem 4.4 is the lower-bound result on which Theorems 5.2, 6.2, and 6.4 all depend, the claimed logspace, P, and NC characterizations are not yet supported by the written proof. This is not merely a request for more exposition: if any of the bricks requires a tier outside {1, 0, -1, -infinity} or an unallowed recursion scheme, the central claims fail.
  2. [Section 6, proofs of Theorems 6.2 and 6.4] The proof of Proposition 4.1 explicitly says that it is given "for non-mutual recursion schemes" and that mutual recursion schemes "follow the same pattern," but no simultaneous version of the tropical interpretation is stated. Mutual recursion is essential to the paper's goal of encoding k log n space, as explained in Section 4.2 and in the Concluding Remarks. Since Corollary 4.2 and Theorem 4.4 rely on the bound for mutually recursive functions, the extension to mutual recursion should be written out rather than deferred; as it stands, the logspace upper bound does not formally cover the mutual recursion schemes used in the central simulation.
  3. [Section 6] The proofs of Theorems 6.2 and 6.4 assume without construction that the predicates IsUniversal and isPositive and the transition maps Next0 and Next1 are L-tropical functions, and they assert that substitutions "amount to alternation" and that the reverse direction follows because each bit of the substituted recursion is a boolean function of bits of two recursive calls. These are nontrivial steps: the reverse direction for P must show that the alternating simulation stays within logarithmic space and polynomial time, and the corresponding statement for NC must establish the polylogarithmic time bound. Since these theorems inherit the unproven simulation of Theorem 4.4, the P and NC characterizations are not yet established by the manuscript.
minor comments (4)
  1. [Section 4] The text refers to "Hoffman's work" where the intended reference is Hofmann; the same misspelling appears in the discussion of non-size increasing types.
  2. [Section 1.3] The definition of the Read construct says that Read(i) = w_i for binary encodings of integers 0 < i <= n and Read(v) = epsilon otherwise, but the typing of Read in Section 4.3 is written as though it always outputs a bit a in {0,1}. The out-of-range behavior and the treatment of the empty word should be made uniform in both places.
  3. [Section 4.3] The notation "t = t1,t2,t3,t4" and the four-tier display of tropical composition is hard to parse; a short explanation of which argument positions may occupy each tier, or a diagram, would improve readability.
  4. [Section 7] The concluding remarks contain typos: "wether" should be "whether" in two places. These do not affect the mathematics.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the tropical algebra is defined independently and checked against external RAM/ATM models; the unconstructed 'simple bricks' are a proof gap, not a circular step.

full rationale

The derivation chain is not circular. The tropical tiering discipline is introduced syntactically via tier values and recursion schemes, before any machine-class equivalence is stated, and the upper bound L-tropical subset of logspace is proved through Proposition 4.1's size inequality plus a structural induction, not by importing logspace. The lower bound of Theorem 4.4 simulates a random-access Turing machine, an external model, and Theorems 5.2, 6.2 and 6.4 inherit that external simulation rather than a self-citation chain. The one genuine weakness is in Section 4.3, proof of Theorem 4.4, paragraph 'Reading and Updating a configuration': the paper states 'With all these simple bricks, and especially with the in-place one-bit replacement, one is then able to read a configuration, and to update it, with L-tropical functions' and asserts the four 'simple bricks' (boolean encoding, scanning, substring extraction, one-bit replacement) are L-tropical without constructing them. The later Theorems 5.2, 6.2 and 6.4 inherit this simulation, so the omitted construction is load-bearing; if any brick needs a tier outside {1, 0, -1, -infinity} or an unallowed recursion scheme, the logspace lower bound is unsupported. That is a real completeness or correctness risk, but it is not circularity: no equation of the paper identifies the target class with the algebra by construction, no fitted parameter is renamed as a prediction, and no load-bearing argument reduces to an unverified self-citation. The mutual-recursion encoding of k log n space is a deliberate design choice, not an equivalence between inputs and outputs. Therefore the circularity score is 0.

Assumptions & free parameters 2 free parameters · 5 assumptions · 4 invented entities

The framework introduces a new tiering discipline and new recursion schemes; no empirical parameters are fitted. The hand-chosen tiers and the four-tier restriction are the key design choices that make the size bounds work. The proofs rely on standard theorems about primitive recursion, safe recursion, and alternating complexity classes.

free parameters (2)
  • Hand-chosen tropic values for basic functions = T1(s0)=T1(s1)=T1(s)=1; T1(tl)=-1; T1(hd)=T1(Read)=-infinity; T_i(Pr^i_n) as given
    These assignments are the mechanism that makes output sizes linear in input sizes; if they were different, the size bounds and the class characterizations would change.
  • Restriction to four tropic values 1, 0, -1, -infinity = four finite tiers
    Chosen to make the tier discipline expressible directly in the syntax; the logspace, P, and NC theorems are proven only for this restriction.
assumptions (5)
  • domain assumption The random-access Turing machine with unit-cost pointer reading is the right model for sub-polynomial complexity classes.
    The whole framework is modelled on the RA TM; cited to Chandra et al. [5], but not proven. A different pointer cost model could shift the polylogtime and logspace characterizations.
  • standard math Primitive recursion on notations over binary strings yields exactly the classical primitive recursive functions.
    Used in Theorem 2.1; standard folk theorem, cited.
  • standard math Bellantoni-Cook safe recursion characterizes Ptime.
    Basis for the adaptation in Theorem 3.1; cited.
  • standard math Alogspace = P and A(logspace,polylogtime) = NC.
    Used in Theorems 6.2 and 6.4; cited to Chandra et al. and Ruzzo.
  • domain assumption The tropical polynomial size interpretation, a max-plus linear bound, is the right invariant for non-size-increasing computation.
    This is the core new definition; its adequacy is not independently benchmarked outside the paper's own proofs.
invented entities (4)
  • Pointer recursion framework with Offset and Read constructs independent evidence
    purpose: Allows recursive functions to access an implicit input at unit cost, mimicking RA TMs
    It is a direct analogue of the random-access Turing machine, an established model. The specific algebra is new.
  • Tropical tiering discipline
    purpose: Syntactically constrains output size to be linear in input sizes, yielding logarithmic space and string sizes
    New, the paper's principal contribution; no external verification beyond the paper's proofs.
  • Mutual recursion schemes of width 2k+3
    purpose: Encodes k log n space as k strings of length log n
    Introduced to make the logspace simulation work.
  • Substitution recursion schemes
    purpose: Encodes alternation by allowing two recursive calls with modified safe arguments
    Introduced to capture P and NC.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pointers in Recursion: Exploring the Tropics." pith.science (2026). https://pith.science/paper/O5OQ2PH5

@misc{pith2026190804922,
  author       = {Pith},
  title        = {Pith review of: Pointers in Recursion: Exploring the Tropics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O5OQ2PH5}},
  note         = {Machine review of arXiv:1908.04922}
}
read the original abstract

We translate the usual class of partial/primitive recursive functions to a pointer recursion framework, accessing actual input values via a pointer reading unit-cost function. These pointer recursive functions classes are proven equivalent to the usual partial/primitive recursive functions. Complexity-wise, this framework captures in a streamlined way most of the relevant sub-polynomial classes. Pointer recursion with the safe/normal tiering discipline of Bellantoni and Cook corresponds to polylogtime computation. We introduce a new, non-size increasing tiering discipline, called tropical tiering. Tropical tiering and pointer recursion, used with some of the most common recursion schemes, capture the classes logspace, logspace/polylogtime, ptime, and NC. Finally, in a fashion reminiscent of the safe recursive functions, tropical tiering is expressed directly in the syntax of the function algebras, yielding the tropical recursive function algebras.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 9 canonical work pages

  1. [1]

    Bill Allen (1991): Arithmetizing Uniform NC . Ann. Pure Appl. Logic 53(1), pp. 1–50, doi:10.1016/0168-0072(91)90057-S

    work page doi:10.1016/0168-0072(91)90057-s 1991

  2. [2]

    Cook (1992): A New Recursion-Theoretic Characterization of the Polytime Functions

    Stephen Bellantoni & Stephen A. Cook (1992): A New Recursion-Theoretic Characterization of the Polytime Functions. Computational Complexity 2, pp. 97–110, doi:10.1007/BF01201998

    doi:10.1007/bf01201998 1992

  3. [3]

    Bloch (1994): Function-Algebraic Characterizations of Log and Polylog P arallel Time

    Stephen A. Bloch (1994): Function-Algebraic Characterizations of Log and Polylog P arallel Time. Compu- tational Complexity 4, pp. 175–205, doi:10.1007/BF01202288

    work page doi:10.1007/bf01202288 1994

  4. [4]

    Guillaume Bonfante, Reinhard Kahle, Jean-Yves Marion & Isabel Oitavem (2016): Two function algebras defining functions in NC k boolean circuits. Inf. Comput. 248, pp. 82–103, doi:10.1016/j.ic.2015.12.009

    work page doi:10.1016/j.ic.2015.12.009 2016

  5. [5]

    Chandra, Dexter Kozen & Larry J

    Ashok K. Chandra, Dexter Kozen & Larry J. Stockmeyer (198 1): Alternation. J. ACM 28(1), pp. 114–133, doi:10.1145/322234.322243

    arXiv

  6. [6]

    Clote (1989): Sequential, machine-independent characterizations of th e parallel com- plexity classes ALOGTIME, AC k, NC k and NC

    P . Clote (1989): Sequential, machine-independent characterizations of th e parallel com- plexity classes ALOGTIME, AC k, NC k and NC . Feasible Mathematics, Birkha¨ user, 49-69 , doi:10.1007/978-1-4612-3466-1 4

    doi:10.1007/978-1-4612-3466-1 1989

  7. [7]

    Cobham (1962): The intrinsic computational difficulty of functions

    A. Cobham (1962): The intrinsic computational difficulty of functions . In Y . Bar-Hillel, editor: Proceed- ings of the International Conference on Logic, Methodology , and Philosophy of Science , North-Holland, Amsterdam, pp. 24–30, doi:10.2307/2270886

    work page doi:10.2307/2270886 1962

  8. [8]

    Martin Hofmann (2003): Linear types and non-size-increasing polynomial time comp utation. Inf. Comput. 183(1), pp. 57–85, doi:10.1016/S0890-5401(03)00009-9

    doi:10.1016/s0890-5401(03)00009-9 2003

Show all 16 references
  1. [9]

    ACM Trans

    Martin Hofmann & Ulrich Sch¨ opp (2010): Pure pointer programs with iteration. ACM Trans. Comput. Log. 11(4), pp. 26:1–26:23, doi:10.1145/1805950.1805956

    2010

  2. [10]

    Computational Complexity 13(1-2), pp

    Satoru Kuroda (2004): Recursion Schemata for Slowly Growing Depth Circuit Classe s. Computational Complexity 13(1-2), pp. 69–89, doi:10.1007/s00037-004-0184-4

    2004 doi

  3. [11]

    In: Proceedings of the Sixth Annual Symposium on Logic in Computer Science (LICS ’91), Am sterdam, The Netherlands, July 15-18, 1991, IEEE Computer Society, pp

    Daniel Leivant (1991): A F oundational Delineation of Computational Feasiblity. In: Proceedings of the Sixth Annual Symposium on Logic in Computer Science (LICS ’91), Am sterdam, The Netherlands, July 15-18, 1991, IEEE Computer Society, pp. 2–11, doi:10.1109/LICS.1991. 151625....

    1991 doi

  4. [12]

    In Leszek Pacholski & Jerzy Tiuryn, editors: CSL, Lecture Notes in Computer Science 933, Springer, pp

    Daniel Leivant & Jean-Yves Marion (1994): Ramified Recurrence and Computational Complexity II: Sub- stitution and Poly-Space . In Leszek Pacholski & Jerzy Tiuryn, editors: CSL, Lecture Notes in Computer Science 933, Springer, pp. 486–500, doi:10.1016/0022-0000(83)90 008-9

    1994 doi

  5. [13]

    Daniel Leivant & Jean-Yves Marion (2000): A characterization of alternating log time by ramified recur - rence. Theor. Comput. Sci. 236(1-2), pp. 193–208, doi:10.1016/S0304-3975(99)00209 -1

    2000 doi

  6. [14]

    Information and Computation , p

    Daniel Leivant & Jean-Yves Marion (2000): Ramified Recurrence and Computational Complexity IV : Predicative Functionals and Poly-Space . Information and Computation , p. 12 p. Available at https://hal.inria.fr/inria-00099077. To appear. Article dans revue scientifique avec comit...

    2000

  7. [15]

    J. C. Lind (1974): Computing in logarithmic space. Technical Report, Massachusetts Institute of Technology

    1974

  8. [16]

    Ruzzo (1981): On Uniform Circuit Complexity

    Walter L. Ruzzo (1981): On Uniform Circuit Complexity . J. Comput. Syst. Sci. 22(3), pp. 365–383, doi:10.1016/0022-0000(81)90038-6

    1981 doi

Pith tools

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