{"ID":2871780,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.10188","arxiv_id":"2509.10188","title":"Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class","abstract":"In this paper, we study the class $\\mathtt{cstPP}$ of operations $\\mathtt{op}: \\mathbb{N}^k\\to\\mathbb{N}$, of any fixed arity $k\\ge 1$, satisfying the following property: for each fixed integer $d\\ge 1$, there exists an algorithm for a RAM machine which, for any input integer $N\\ge 2$, - pre-computes some tables in $O(N)$ time, - then reads $k$ operands $x_1,\\ldots,x_k\u003cN^d$ and computes $\\mathtt{op}(x_1,\\dots,x_k)$ in constant time. We show that the $\\mathtt{cstPP}$ class is robust and extensive and satisfies several closure properties. It is invariant depending on whether the set of primitive operations of the RAM is $\\{+\\}$, or $\\{+,-,\\times,\\mathtt{div},\\mathtt{mod}\\}$, or any set of operations in $\\mathtt{cstPP}$ provided it includes $+$. We prove that the $\\mathtt{cstPP}$ class is closed under composition and, for fast-growing functions, is closed under inverse. We also show that in the definition of $\\mathtt{cstPP}$ the constant-time procedure can be reduced to a single return instruction. Finally, we establish that linear preprocessing time is not essential in the definition of the $\\mathtt{cstPP}$ class: this class is not modified if the preprocessing time is increased to $O(N^c)$, for any fixed $c\u003e1$, or conversely, is reduced to $N^{\\varepsilon}$, for any positive $\\varepsilon\u003c1$ (provided the set of primitive operation includes $+$, $\\mathtt{div}$ and $\\mathtt{mod}$). To complete the picture, we demonstrate that the $\\mathtt{cstPP}$ class degenerates if the preprocessing time reduces to $N^{o(1)}$.","short_abstract":"In this paper, we study the class $\\mathtt{cstPP}$ of operations $\\mathtt{op}: \\mathbb{N}^k\\to\\mathbb{N}$, of any fixed arity $k\\ge 1$, satisfying the following property: for each fixed integer $d\\ge 1$, there exists an algorithm for a RAM machine which, for any input integer $N\\ge 2$, - pre-computes some tables in $O(...","url_abs":"https://arxiv.org/abs/2509.10188","url_pdf":"https://arxiv.org/pdf/2509.10188v1","authors":"[\"Étienne Grandjean\",\"Louis Jachiet\"]","published":"2025-09-12T12:28:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}