pith. sign in

arxiv: 2606.01175 · v1 · pith:LITLQFC7new · submitted 2026-05-31 · 💻 cs.CC

On the Complexity of Recurrence Evaluation

Artem Parfenov , Michael Vyalyi This is my paper

Pith reviewed 2026-06-28 15:59 UTC · model grok-4.3

classification 💻 cs.CC
keywords recurrence evaluationPSPACE-completeEXP-completePP-hardNAND recurrencesimpartial gamescomputational complexity
0
0 comments X

The pith

Evaluating fixed recurrences on sequences is PSPACE-complete for unary offsets and EXP-complete for binary offsets.

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

The paper studies the complexity of evaluating finitely valued recurrent functions with a fixed defining function but variable offsets supplied in the input. For one-dimensional sequences, the problem is PSPACE-complete when offsets are given in unary notation and EXP-complete when given in binary. For NAND-defined recurrences on a three-dimensional grid using only unit coordinate offsets, the evaluation problem remains PP-hard even when arbitrary boundary conditions are allowed. These results link recurrence evaluation to the complexity of impartial games under generalized winning conditions.

Core claim

We show that the recurrence evaluation problem is PSPACE-complete when offsets are given in unary and EXP-complete when given in binary, for sequences with a fixed recurrence relation. Additionally, for recurrences defined by the NAND function on a 3-dimensional grid with coordinate offsets, the problem is PP-hard with arbitrary boundary conditions.

What carries the argument

The recurrence evaluation problem with a fixed finite-valued defining function and input-provided offsets or boundary conditions.

If this is right

  • The problem remains hard for sequences when the recurrence is fixed.
  • Binary encoding of offsets increases the complexity to EXP.
  • PP-hardness holds for 3D NAND recurrences even with arbitrary boundaries.
  • These connect to impartial games with normal and misère conditions generalized.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If true, similar hardness may apply to other fixed functions beyond NAND.
  • The results suggest that grid-based recurrences capture game-theoretic hardness.
  • Extensions could explore higher dimensions or different offset sets.

Load-bearing premise

The recurrence function is fixed and takes only finitely many values, while offsets and boundaries vary as input.

What would settle it

Discovery of a polynomial-space algorithm for the binary-offset case would contradict the EXP-completeness result.

Figures

Figures reproduced from arXiv: 2606.01175 by Artem Parfenov, Michael Vyalyi.

Figure 4.1
Figure 4.1. Figure 4.1: Unrolling (5) for two steps: the value at (x, y, z) on layer t + 2 depends on six points on layer t. These six points form a triangle of side 2, which maps to a triangle of side 1 on layer t + 1, and then to the target point on layer t + 2. As illustrated in [PITH_FULL_IMAGE:figures/full_fig_p009_4_1.png] view at source ↗
Figure 4.2
Figure 4.2. Figure 4.2: Evolution of a triangle in configuration [PITH_FULL_IMAGE:figures/full_fig_p010_4_2.png] view at source ↗
Figure 4.3
Figure 4.3. Figure 4.3: Evolution of the bounding triangle. The configuration shrinks and the diagonal [PITH_FULL_IMAGE:figures/full_fig_p011_4_3.png] view at source ↗
Figure 4.4
Figure 4.4. Figure 4.4: The three gadgets: a vertical strip (left), a horizontal strip (center), and a corner connecting vertical [PITH_FULL_IMAGE:figures/full_fig_p011_4_4.png] view at source ↗
Figure 4.5
Figure 4.5. Figure 4.5: The configuration I(η, ξ). Lemma 10. ϕ ∈ I(η, ξ)Tgadget/2 iff (η, ξ) ∈ SymBF. Proof. The proof relies on tracking the minimum sum of coordinates of the evolving configurations I(η, ξ)t. Let smin(U) denote the minimum sum of coordinates u + v for points (u, v) ∈ U. For the initial configuration I(η, ξ) = I(η, ξ)0 we have smin(I(η, ξ)0) = −4. Thus, smin(Ut) ≥ −4 + t due to Lemma 6. So, the minimum coordina… view at source ↗
read the original abstract

In this paper, we study the complexity of the recurrence evaluation problem. We are interested in finitely valued recurrent functions. We present two results in this direction. First, we study the recurrence problem for sequences, assuming that a recurrence relation is defined by a fixed function, while the offsets are part of the input. Depending on the form of presentation (whether the offsets are given in unary or in binary), the problem is PSPACE-complete or EXP-complete. Second, we study recurrences defined by the NAND function. They are related to impartial games. We prove PP-hardness of the recurrence evaluation problem for a very simple 3-dimensional game, in which the offset vectors are coordinate vectors (1,0,0), (0,1,0) and (0,0,1) but the boundary conditions are arbitrary. In other words, we consider generalized winning conditions for the game extending the normal and the mis\`ere winning conditions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper studies the complexity of evaluating finitely valued recurrent functions. It claims two main results: (1) when a recurrence is defined by a fixed function and offsets are part of the input, the evaluation problem is PSPACE-complete if offsets are encoded in unary and EXP-complete if encoded in binary; (2) the evaluation problem for NAND-defined recurrences on a 3D grid with unit coordinate offsets (1,0,0), (0,1,0), (0,0,1) and arbitrary boundary conditions is PP-hard. The second result is framed in terms of generalized impartial games extending normal and misère play.

Significance. If the claims are substantiated with complete reductions and membership arguments, the results would give tight complexity classifications for recurrence evaluation, linking a simple dynamic-programming-style problem to PSPACE/EXP and a 3D grid game to PP. The explicit connection to impartial games and the use of fixed recurrence functions with variable offsets or boundaries are potentially useful for classifying other DP and game problems.

major comments (1)
  1. [Abstract] Abstract (second result): the PP-hardness claim for NAND recurrences on the 3D grid assumes arbitrary boundary conditions are supplied as part of the input while the recurrence function is fixed. When target coordinates are given in binary (to be consistent with the EXP-completeness case of the first result), an arbitrary boundary function on the three coordinate planes requires either an exponential-sized explicit table or a compact encoding (circuit/formula). The abstract supplies no indication of which encoding is used; without a polynomial-size encoding the input size becomes exponential in the coordinate values, which would invalidate both PP membership and standard poly-time reductions for hardness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for highlighting the need for greater clarity in the abstract regarding the encoding of boundary conditions. We address the major comment below and will revise the manuscript to improve precision.

read point-by-point responses

  1. Referee: [Abstract] Abstract (second result): the PP-hardness claim for NAND recurrences on the 3D grid assumes arbitrary boundary conditions are supplied as part of the input while the recurrence function is fixed. When target coordinates are given in binary (to be consistent with the EXP-completeness case of the first result), an arbitrary boundary function on the three coordinate planes requires either an exponential-sized explicit table or a compact encoding (circuit/formula). The abstract supplies no indication of which encoding is used; without a polynomial-size encoding the input size becomes exponential in the coordinate values, which would invalidate both PP membership and standard poly-time reductions for hardness.

    Authors: We agree the abstract is insufficiently precise on this point. The full paper encodes the arbitrary boundary conditions via a compact polynomial-size circuit (or equivalent succinct representation) that, given any coordinate on the three boundary planes, outputs the boundary value. This ensures the overall input remains polynomial in the bit length of the target coordinates, supporting both PP membership (via the standard PP machine for evaluating the recurrence with the circuit oracle) and the correctness of the poly-time reductions used for PP-hardness. We will revise the abstract to state explicitly that boundaries are supplied via a compact encoding such as a circuit. revision: yes

Circularity Check

0 steps flagged

No circularity: hardness results rest on explicit reductions from standard problems

full rationale

The paper establishes PSPACE/EXP-completeness and PP-hardness via direct reductions from known complete problems (e.g., quantified Boolean formulas or impartial games) to recurrence evaluation with fixed NAND or other functions and variable offsets/boundaries. No equations, parameters, or self-citations are used to define the target complexity class in terms of itself; the input encoding of boundaries is part of the problem statement rather than a fitted quantity renamed as a prediction. The derivation chain is therefore independent of the claimed results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on standard complexity-theoretic reductions and the assumption that the defining functions are fixed while offsets or boundaries vary; no free parameters, invented entities, or non-standard axioms are visible in the abstract.

axioms (1)
  • domain assumption Standard complexity classes (PSPACE, EXP, PP) and their closure properties under reductions are well-defined and distinct.
    Invoked implicitly when classifying the problems as complete or hard for these classes.

pith-pipeline@v0.9.1-grok · 5685 in / 1110 out tokens · 18772 ms · 2026-06-28T15:59:52.347440+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 10 canonical work pages

  1. [1]

    AMS, 2003

    Graham Everest, Poorten Alf van der, Igor Shparlinski, and Thomas Ward.Recurrence Sequences. AMS, 2003

    2003

  2. [2]

    An Algorithm for Evaluation of Remote Terms in A Linear Recurrence Sequence

    J. C. P. Miller and D. J. Spencer Brown. “An Algorithm for Evaluation of Remote Terms in A Linear Recurrence Sequence”. In:Comput. J.9.2 (1966), pp. 188–190

    1966

  3. [3]

    An efficient formula for linear recurrences

    C. M. Fiduccia. “An efficient formula for linear recurrences”. In:SIAM Journal on computing14.1 (1985), pp. 106–112

    1985

  4. [4]

    Efficient computations in terms of linear recurrence sequences of any order

    Dmitry I. Khomovsky. “Efficient computations in terms of linear recurrence sequences of any order”. In: Integers: Electronic Journal of Combinatorial Number Theory18 (2018), #A39

    2018

  5. [5]

    A mathematical investigation of games of “take-away

    Solomon W. Golomb. “A mathematical investigation of games of “take-away””. In:Journal of Combinatorial Theory1.4 (1966), pp. 443–458.issn: 0021-9800.doi:https://doi.org/10.1016/S0021-9800(66)80016-9. url:https://www.sciencedirect.com/science/article/pii/S0021980066800169

    work page doi:10.1016/s0021-9800(66)80016-9 1966

  6. [6]

    Unsolved Problems in Combinatorial Games

    Richard K. Guy. “Unsolved Problems in Combinatorial Games”. In:Combinatorics Advances. Ed. by Charles J. Colbourn and Ebadollah S. Mahmoodian. Boston, MA: Springer US, 1995, pp. 161–179.isbn: 978-1-4613- 3554-2.doi:10.1007/978-1-4613-3554-2_10.url:https://doi.org/10.1007/978-1-4613-3554-2_10

    work page doi:10.1007/978-1-4613-3554-2_10.url:https://doi.org/10.1007/978-1-4613-3554-2_10 1995

  7. [7]

    ‘An equilibrium existence result for an economy with land’

    Ingo Althöfer and Jörg Bültermann. “Superlinear period lengths in some subtraction games”. In:Theoretical Computer Science148.1 (1995), pp. 111–119.issn: 0304-3975.doi:https://doi.org/10.1016/0304- 3975(95)00019-S.url:https://www.sciencedirect.com/science/article/pii/030439759500019S

    work page doi:10.1016/0304- 1995

  8. [8]

    On the expansion of three-element subtraction sets

    Nhan Bao Ho. “On the expansion of three-element subtraction sets”. In:Theoretical Computer Science582 (2015), pp. 35–47.issn: 0304-3975.doi:https://doi.org/10.1016/j.tcs.2015.03.025.url:https: //www.sciencedirect.com/science/article/pii/S0304397515002418

    work page doi:10.1016/j.tcs.2015.03.025.url:https: 2015

  9. [9]

    On the linearity of the periods of subtraction games

    Shenxing Zhang. “On the linearity of the periods of subtraction games”. In:Theoretical Computer Science 985 (2024), p. 114350.issn: 0304-3975.doi:https://doi.org/10.1016/j.tcs.2023.114350.url: https://www.sciencedirect.com/science/article/pii/S0304397523006631

    work page doi:10.1016/j.tcs.2023.114350.url: 2024

  10. [10]

    Superpolynomial period lengths of the winning positions in the subtraction game

    István Miklós and Logan Post. “Superpolynomial period lengths of the winning positions in the subtraction game”. In:Int. J. Game Theory53.4 (2024), pp. 1275–1313.doi:10.1007/S00182-024-00911-5.url: https://doi.org/10.1007/s00182-024-00911-5

    work page doi:10.1007/s00182-024-00911-5.url: 2024

  11. [11]

    Urban Larsson and Johan Wästlund.From heaps of matches to the limits of computability. 2012. arXiv: 1202.0664 [cs.CC].url:https://arxiv.org/abs/1202.0664. 15

    Pith/arXiv arXiv 2012

  12. [12]

    On Computational Hardness of Multidimensional Subtraction Games

    Vladimir Gurvich and Mikhail Vyalyi. “On Computational Hardness of Multidimensional Subtraction Games”. In:Algorithms14.3 (2021).issn: 1999-4893.doi:10.3390/a14030071.url:https://www.mdpi.com/1999- 4893/14/3/71

    work page doi:10.3390/a14030071.url:https://www.mdpi.com/1999- 2021

  13. [13]

    More about exact slow k-Nim

    Nikolay Chikin, Vladimir Gurvich, Konstantin Knop, Michael S. Paterson, and Michael Vyalyi. “More about exact slow k-Nim”. In:Integers: Electronic Journal of Combinatorial Number Theory21 (2021), #G4

    2021

  14. [14]

    On Remoteness Functions of Exact Slowk-NIM withk+ 1Piles

    Vladimir Gurvich, Denis Martynov, Vladislav Maximchuk, and Michael Vyalyi. “On Remoteness Functions of Exact Slowk-NIM withk+ 1Piles”. In:Integers: Electronic Journal of Combinatorial Number Theory24 (2024), #G1

    2024

  15. [15]

    G., Naranjo, S., Rideout, W

    Urban Larsson, Indrajit Saha, and Makoto Yokoo. “Subtraction games in more than one dimension”. In: Theoretical Computer Science1016 (2024), p. 114775.issn: 0304-3975.doi:https://doi.org/10.1016/j. tcs.2024.114775.url:https://www.sciencedirect.com/science/article/pii/S030439752400392X

    work page doi:10.1016/j 2024

  16. [16]

    Sipser.Introduction to the Theory of Computation

    M. Sipser.Introduction to the Theory of Computation. Cengage Learning, 2012.isbn: 9781285401065.url: https://books.google.ru/books?id=1aMKAAAAQBAJ

    2012

  17. [17]

    Arora and B

    S. Arora and B. Barak.Computational Complexity: A Modern Approach. Cambridge University Press, 2006. isbn: 978-0-521-42426-4.url:https://theory.cs.princeton.edu/complexity/book.pdf

    2006

  18. [18]

    Ding-Zhu Du and Ker-I Ko.Theory of Computational Complexity. 2nd ed. John Wiley & Sons, Inc., 2014. isbn: 9781118306086

    2014

  19. [19]

    Ryan Williams and Seri Khoury.Functions With and Without Small Circuits. Sept. 2018.url:https: //people.csail.mit.edu/rrw/cs294-2018/fns-without-small2.pdf

    2018

  20. [20]

    The Complexity of Algorithmic Problems on Succinct Instances

    José L. Balcázar, Antoni Lozano, and Jacobo Torán. “The Complexity of Algorithmic Problems on Succinct Instances”. In:Computer Science. Springer, 1992, pp. 351–377.doi:10.1007/978-1-4615-3422-8_30

    work page doi:10.1007/978-1-4615-3422-8_30 1992

  21. [21]

    Succinct circuit representations and leaf language classes are basically the same concept

    Bernd Borchert and Antoni Lozano. “Succinct circuit representations and leaf language classes are basically the same concept”. In:Information Processing Letters59.4 (1996), pp. 211–215.doi:10.1016/0020-0190(96) 00096-8. 16

    work page doi:10.1016/0020-0190(96 1996