Capabilities and complexity of computations with integer division

Abstract

Computation trees with operation set S $\subseteq$ {+, −,*, DIV, DIV_c} (S-CTs) are considered. DIV denotes integer division, DIVinc integer division by constants. We characterize the families of languages L $\subseteq$ ℤⁿ 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$ ℤⁿ that can be recognized by an S-CT. In [7], CC ₁ {S} is characterized for all S $\subseteq$ {+, −, *, DIV, DIV_c} It turns out that CC ₁({+,−,DIV_c})=CC ₁ {+,−,*, 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≥ 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. Ω(n ²) 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 Ω(loglog(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).

Supported in part by DFG Grant Di 412-1