Summary: Computation trees with operation set \(S\subseteq\{+,-,*,DIV,DIV_ c\}\) \((S-CTs)\) are considered. \(DIV\) denotes integer division, \(DIV_ c\) integer division by constants. We characterize the families of languages \(L\subseteq{\mathbb{Z}}^ n\) that can be recognized by \(S-CTs\), separate the computational capabilities of \(S-CTs\) for different operation sets \(S\), and prove lower bounds for the depth of such trees.
Let \(CC_ n(S)\) denote the family of languages \(L\subseteq{\mathbb{Z}}^ n\) that can be recognized by an \(S-CT\). In [B. Just, F. Meyer auf der Heide and A. Wigderson, RAIRO, Inf. Theor. Appl. 23, No. 1, 101- 111 (1989; Zbl 0665.68027)], \(CC_ 1\{S\}\) is characterized for all \(S\subseteq\{+,-,*, DIV, DIV_ c\}\). It turns out that \(CC_ 1(\{+,- ,DIV_ c\})=CC_ 1\{+,-,*,DIV\}\).
In this paper we shed some more light on the computational power of integer division:
– We characterize \(CC_ n(S)\), \(n>1\), for \(S=\{+,-,DIV_ c\}\) and \(S=\{+,-,*,DIV_ c\}\), and partially characterize \(CC_ n(S)\), \(n\geq 1\), for \(S=\{+,-,DIV\}\) and \(S=\{+,-,*,DIV\}\).
– We completely determine the relations among the classes \(CC_ n(S)\).
We further prove lower bounds:
– The component counting lower bound (e.g. \(\Omega(n^ 2)\) for the knapsack problem) proven for \(S=\{+,-,*\}\) by Ben Or and Yao also holds for \(\{+,-,*,DIV_ c\}\).
– The GCD-algorithm due to Brent and Kung for \(\{+,-,DIV_ c\}\)-CTs is optimal even for \(\{+,-,DIV\}\)-CTs.
– Testing whether \(q(y)>x\) for an irreducible polynomial \(q\) of degree \(d\) takes time \(\Omega(\log\log(d))\) for \(\{+,-,*,DIV\}\)-CTs, even if arbitrary rational constants can be used at unit cost. This is the first nontrivial lower bound in this strong model (in which, e.g., every finite language can be recognized in constant time, independent of the size of the language).
For the entire collection see [Zbl 0866.00060].