Squaresville

Given a function from some domain to itself, we can form its 'square' f^2(x) = f(f(x)); third, fourth powers likewise.

How about the inverse problem, 'fractional powers'? What conditions on f allow us to express our function as f(x) = g(g(x)) for some g?

Puzzle: in the case where the domain is a set of nodes and f is presented as a directed graph with outdegree 1 (each u points to f(u)), try and classify the problem of recognizing squares as in P or NP-complete.

(for a quick intro to P and NP, see the wiki page).

And what if the domain is the real or complex numbers? Here we're courting higher math, but Taylor expansions offer some guidance. There's a thought-provoking if hand-wavy discussion of the real case here; for more authoritative references (which I haven't read) this page looks promising.

Complex numbers have nice properties; do fractional iterates exist more frequently in this case? I haven't thought much about this, but am reminded of a nifty result from a college course: If f(z) is an analytic function, then either f(z) has a fixed point OR h(z) = f(f(z)) has one. The proof is short and sweet once you assume the deep result of Picard, that any such f has image equal to the whole complex plane minus at most one point.