2. Complexity
-
Problem 2.1.
[Julia Knight] Let $K$ be an algebraically closed field of characteristic 0, and let $G$ be an ordered divisible group. Consider the Hahn field, defined as follows: $$ K((G)) = \left\{\sum_{g\in S}a_g t^g \mid S\subseteq G \text{ well-ordered}, a_g\in K\right\} $$
If $K$ and $G$ are computable and $f\in K((G))[X]$, how complex is it to determine a root of $f$? At each step, the procedure should produce the next term in a root of $f$, based on the $a_g$ in the input coefficients of $f$. For each step $\alpha$, how many jumps over these coefficients are needed to do step $\alpha$?
Cite this as: AimPL: Definability and decidability problems in number theory, available at http://aimpl.org/definedecide.