Degrees of Second and Higher-Order Polynomials
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 operat...
Main Authors: | , |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2023
|
Subjects: | |
Online Access: | http://arxiv.org/abs/2305.03439 |
id |
ftarxivpreprints:oai:arXiv.org:2305.03439 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:2305.03439 2023-09-05T13:17:04+02:00 Degrees of Second and Higher-Order Polynomials Lim, Donghyun Ziegler, Martin 2023-05-05 http://arxiv.org/abs/2305.03439 unknown http://arxiv.org/abs/2305.03439 Computer Science - Logic in Computer Science Computer Science - Computational Complexity Mathematics - Logic 68Q15 03D15 03D65 F.1.3 G.2.3 I.1.1 text 2023 ftarxivpreprints 2023-08-16T17:41:02Z 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 composition. Text Arctic ArXiv.org (Cornell University Library) Arctic |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Computer Science - Logic in Computer Science Computer Science - Computational Complexity Mathematics - Logic 68Q15 03D15 03D65 F.1.3 G.2.3 I.1.1 |
spellingShingle |
Computer Science - Logic in Computer Science Computer Science - Computational Complexity Mathematics - Logic 68Q15 03D15 03D65 F.1.3 G.2.3 I.1.1 Lim, Donghyun Ziegler, Martin Degrees of Second and Higher-Order Polynomials |
topic_facet |
Computer Science - Logic in Computer Science Computer Science - Computational Complexity Mathematics - Logic 68Q15 03D15 03D65 F.1.3 G.2.3 I.1.1 |
description |
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 composition. |
format |
Text |
author |
Lim, Donghyun Ziegler, Martin |
author_facet |
Lim, Donghyun Ziegler, Martin |
author_sort |
Lim, Donghyun |
title |
Degrees of Second and Higher-Order Polynomials |
title_short |
Degrees of Second and Higher-Order Polynomials |
title_full |
Degrees of Second and Higher-Order Polynomials |
title_fullStr |
Degrees of Second and Higher-Order Polynomials |
title_full_unstemmed |
Degrees of Second and Higher-Order Polynomials |
title_sort |
degrees of second and higher-order polynomials |
publishDate |
2023 |
url |
http://arxiv.org/abs/2305.03439 |
geographic |
Arctic |
geographic_facet |
Arctic |
genre |
Arctic |
genre_facet |
Arctic |
op_relation |
http://arxiv.org/abs/2305.03439 |
_version_ |
1776198392859328512 |