Second-order polynomials generalize classical (=first-order) ones in allowing for additional variables that range over functions rather than values. We are motivated by their applications in higher-order computational complexity theory, extending for instance discrete classes (like P/FP or PSPACE/FPSPACE) to operators in Analysis [http://doi.org/10.1137/S0097539794263452], [http://doi.org/10.1145/2189778.2189780]. The degree subclassifies ordinary polynomial growth into linear, quadratic, cubic, etc. To similarly classify second-order polynomials, we (well-)define their degree by structural induction as an "arctic" first-order polynomial: a term/expression over integer variable D and operations + and ⋅ and binary max(). This generalized degree turns out to transform nicely under (now two kinds of) polynomial composition. As examples, we collect and determine the degrees of previous and new asymptotic analyses of algorithms and operators receiving function/oracle arguments. Then we motivate and introduce third-order polynomials and their degrees as arctic second-order polynomials, along with their transformations under three kinds of composition. Proceeding to fourth order and beyond yields a hierarchy, with characterization in Simply Typed Lambda Calculus.

When encoding real numbers as (necessarily infinite) bit-strings, the naïve binary/decimal expansion is well-known [ doi:10.1112/plms/s2-43.6.544 ] computably “ un reasonable”, rendering, for example, tripling qualitatively discontinuous on Cantor’s sequence space. Encoding reals as sequences of (finite integer numerators and denominators, in binary, of) rational approximations does make common operations qualitatively computable, yet admits no bounds on their computational complexity/quantitative continuity. Dyadic approximations, on the other hand, are known polynomially, and signed binary expansions even linearly, “reasonable” in a rigorous sense recalled in the introduction of this work. But how to distinguish between un/suitable encodings of spaces common in Calculus beyond the reals, such as Banach or Sobolev? With respect to qualitative computability/continuity on topological spaces, the technical condition of admissibility had been identified [ doi:10.1016/0304-3975(85)90208-7 ] for an encoding over Cantor space (historically called a representation ) to be “reasonable” [ doi:10.1007/978-3-030-59234-9_9 ] . Roughly speaking, admissibility requires the representation to be (i) continuous, and to be (ii) maximal with respect to continuous reduction. Admissible representations exist for a large class of spaces. And for (precisely) these does the Kreitz–Weihrauch—sometimes aka Main —Theorem of Computable Analysis hold, which characterizes continuity of functions by continuity of mappings translating codes, so-called realizers . We refine qualitative computability/continuity on topological spaces to quantitative continuity/complexity on metric spaces by proposing a notion, and investigating the properties, of polynomially/linearly admissible representations. Roughly speaking, these are (i) close to “optimally” continuous, namely linearly/polynomially relative to the space’s entropy, and they are (ii) maximal with respect to relative linear/polynomial quantitatively continuous reductions defined in the main text. Quantitatively admissible representations are closed under composition over generalized ground spaces beyond Cantor’s. Such representations exhibit a quantitative strengthening of the qualitative Main Theorem , namely now characterizing quantitative continuity of functions by quantitative continuity of realizers. A large class of compact metric spaces is shown to admit polynomially admissible representations over compact ultra metric spaces, and some even a generalization of the linearly admissible signed binary encoding. Quantitative admissibility thus provides the desired criterion for complexity-theoretically “reasonable” encodings.