The computational content of multidimensional discontinuity
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929425655791616 |
|---|---|
| author | Hölzl, Rupert Ng, Keng Meng |
| author_facet | Hölzl, Rupert Ng, Keng Meng |
| contents | The Weihrauch degrees are a tool to gauge the computational difficulty of mathematical problems. Often, what makes these problems hard is their discontinuity. We look at discontinuity in its purest form, that is, at otherwise constant functions that make a single discontinuous step along each dimension of their underlying space. This is an extension of previous work of Kihara, Pauly, Westrick from a single dimension to multiple dimensions. Among other results, we obtain strict hierarchies in the Weihrauch degrees, one of which orders mathematical problems by the richness of the truth-tables determining how discontinuous steps influence the output. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04338 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The computational content of multidimensional discontinuity Hölzl, Rupert Ng, Keng Meng Logic 03D78, 03D30, 03F60 The Weihrauch degrees are a tool to gauge the computational difficulty of mathematical problems. Often, what makes these problems hard is their discontinuity. We look at discontinuity in its purest form, that is, at otherwise constant functions that make a single discontinuous step along each dimension of their underlying space. This is an extension of previous work of Kihara, Pauly, Westrick from a single dimension to multiple dimensions. Among other results, we obtain strict hierarchies in the Weihrauch degrees, one of which orders mathematical problems by the richness of the truth-tables determining how discontinuous steps influence the output. |
| title | The computational content of multidimensional discontinuity |
| topic | Logic 03D78, 03D30, 03F60 |
| url | https://arxiv.org/abs/2405.04338 |