Complexity theory for spaces of integrable functions
This paper investigates second-order representations in the sense of Kawamura and Cook for spaces of integrable functions that regularly show up in analysis. It builds upon prior work about the space of continuous functions on the unit interval: Kawamura and Cook introduced a representation inducing...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2017-09-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/3924/pdf |
| _version_ | 1827322835060654080 |
|---|---|
| author | Florian Steinberg |
| author_facet | Florian Steinberg |
| author_sort | Florian Steinberg |
| collection | DOAJ |
| description | This paper investigates second-order representations in the sense of Kawamura
and Cook for spaces of integrable functions that regularly show up in analysis.
It builds upon prior work about the space of continuous functions on the unit
interval: Kawamura and Cook introduced a representation inducing the right
complexity classes and proved that it is the weakest second-order
representation such that evaluation is polynomial-time computable. The first
part of this paper provides a similar representation for the space of
integrable functions on a bounded subset of Euclidean space: The weakest
representation rendering integration over boxes is polynomial-time computable.
In contrast to the representation of continuous functions, however, this
representation turns out to be discontinuous with respect to both the norm and
the weak topology. The second part modifies the representation to be continuous
and generalizes it to Lp-spaces. The arising representations are proven to be
computably equivalent to the standard representations of these spaces as metric
spaces and to still render integration polynomial-time computable. The family
is extended to cover Sobolev spaces on the unit interval, where less basic
operations like differentiation and some Sobolev embeddings are shown to be
polynomial-time computable. Finally as a further justification quantitative
versions of the Arzel\`a-Ascoli and Fr\'echet-Kolmogorov Theorems are presented
and used to argue that these representations fulfill a minimality condition. To
provide tight bounds for the Fr\'echet-Kolmogorov Theorem, a form of
exponential time computability of the norm of Lp is proven. |
| first_indexed | 2024-04-25T01:35:07Z |
| format | Article |
| id | doaj.art-0120fc515de5447e8b5989a32c2f3e7f |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:07Z |
| publishDate | 2017-09-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-0120fc515de5447e8b5989a32c2f3e7f2024-03-08T09:51:11ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742017-09-01Volume 13, Issue 310.23638/LMCS-13(3:21)20173924Complexity theory for spaces of integrable functionsFlorian SteinbergThis paper investigates second-order representations in the sense of Kawamura and Cook for spaces of integrable functions that regularly show up in analysis. It builds upon prior work about the space of continuous functions on the unit interval: Kawamura and Cook introduced a representation inducing the right complexity classes and proved that it is the weakest second-order representation such that evaluation is polynomial-time computable. The first part of this paper provides a similar representation for the space of integrable functions on a bounded subset of Euclidean space: The weakest representation rendering integration over boxes is polynomial-time computable. In contrast to the representation of continuous functions, however, this representation turns out to be discontinuous with respect to both the norm and the weak topology. The second part modifies the representation to be continuous and generalizes it to Lp-spaces. The arising representations are proven to be computably equivalent to the standard representations of these spaces as metric spaces and to still render integration polynomial-time computable. The family is extended to cover Sobolev spaces on the unit interval, where less basic operations like differentiation and some Sobolev embeddings are shown to be polynomial-time computable. Finally as a further justification quantitative versions of the Arzel\`a-Ascoli and Fr\'echet-Kolmogorov Theorems are presented and used to argue that these representations fulfill a minimality condition. To provide tight bounds for the Fr\'echet-Kolmogorov Theorem, a form of exponential time computability of the norm of Lp is proven.https://lmcs.episciences.org/3924/pdfcomputer science - computational complexity |
| spellingShingle | Florian Steinberg Complexity theory for spaces of integrable functions Logical Methods in Computer Science computer science - computational complexity |
| title | Complexity theory for spaces of integrable functions |
| title_full | Complexity theory for spaces of integrable functions |
| title_fullStr | Complexity theory for spaces of integrable functions |
| title_full_unstemmed | Complexity theory for spaces of integrable functions |
| title_short | Complexity theory for spaces of integrable functions |
| title_sort | complexity theory for spaces of integrable functions |
| topic | computer science - computational complexity |
| url | https://lmcs.episciences.org/3924/pdf |
| work_keys_str_mv | AT floriansteinberg complexitytheoryforspacesofintegrablefunctions |