Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class

Étienne Grandjean, Louis Jachiet

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…