Degrees of Second and Higher-Order Polynomials ...

• Main Authors: Lim, Donghyun, Ziegler, Martin
• Format: Report
• Language: unknown
• Published: arXiv 2023
• Subjects: Logic in Computer Science cs.LO; Computational Complexity cs.CC; Logic math.LO; FOS Computer and information sciences; FOS Mathematics; F.1.3; G.2.3; I.1.1; 68Q15, 03D15, 03D65; Arctic
• Online Access: https://dx.doi.org/10.48550/arxiv.2305.03439; https://arxiv.org/abs/2305.03439

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 example classical classes like P or PSPACE to operators in Analysis [doi:10.1137/S0097539794263452, doi:10.1145/2189778.2189780]. The degree subclassifies ordinary polynomial growth into linear, quadratic, cubic etc. In order to similarly classify second-order polynomials, define their degree to be an 'arctic' first-order polynomial (namely a term/expression over variable $D$ and operations $+$ and $\cdot$ and $\max$). This degree turns out to transform as nicely under (now two kinds of) polynomial composition as the ordinary one. We also establish a normal form and semantic uniqueness for second-order polynomials. Then we define the degree of a third-order polynomial to be an arctic second-order polynomial, and establish its transformation under three kinds of ...