Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915491845505024 |
|---|---|
| author | Grandjean, Étienne Jachiet, Louis |
| author_facet | Grandjean, Étienne Jachiet, Louis |
| contents | 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<N^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>1$, or conversely, is reduced to $N^{\varepsilon}$, for any positive $\varepsilon<1$ (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)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10188 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class Grandjean, Étienne Jachiet, Louis Data Structures and Algorithms Computational Complexity 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<N^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>1$, or conversely, is reduced to $N^{\varepsilon}$, for any positive $\varepsilon<1$ (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)}$. |
| title | Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2509.10188 |