Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-057 | 16th May 2004 00:00

Structural and Computational Complexity of Isometries and their Shift Commutators



{\bf Abstract}

Isometries on formal power series over the finite field $\ff_2$
or on $2$--adic integers can be
computed by invertible transducers on inputs from $\{0,1\}^\infty$.
We consider the structural complexity of an isometry $f$,
measured as {\it tree complexity} $T(f,h)$, $h$ the tree height
[H.~Niederreiter, M.~Vielhaber, {\it J.~Cpx.}, 12 (1996)]
and the computational complexity, as {\it number of bit operations}
$B(f,n)$ needed for the first $n$ input / output symbols.

We introduce the shift commutator
$\SC(f) := \sigma^{-1}\circ f^{-1}\circ \sigma\circ f$ ($\sigma$ the shift on
and show\ \
that $f\mapsto \SC(f)$ is a selfmap on the set of all isometries.
We obtain the polynomial bounds $T(\SC(f),h) \leq T(f,h)^2 - T(f,h) + 2$
and $B(f,n) \leq n\cdot B(\SC(f),n))$, by simulating $f$ by $n$ copies of

On the other hand, trying to bound $T(f,h)$ by $T(\SC(f),h)$
it turns out that {\it e.g.} for the isometries
connected to the continued fraction expansion and
to Collatz' 3N+1 conjecture, the function $f$ itself is structurally
{\it exponentially} more complex than its $\SC(f)$. Hence simulating $f$ by
$\SC(f)$ may yield sharper upper bounds for the bit complexity as can be
inferred from $f$ alone.

We finish with some dynamical aspects of isometries like orbits, ergodicity,
preservation of measure.

ISSN 1433-8092 | Imprint