| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

2. Complexity

    1. 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.