Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2405.00327 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914778728890368 |
|---|---|
| author | Okada, Naoaki Kijima, Shuji |
| author_facet | Okada, Naoaki Kijima, Shuji |
| contents | This work is motivated by a question whether it is possible to calculate a chaotic sequence efficiently, e.g., is it possible to get the $n$-th bit of a bit sequence generated by a chaotic map, such as $β$-expansion, tent map and logistic map in $\mathrm{o}(n)$ time/space? This paper gives an affirmative answer to the question about the space complexity of a tent map. We show that the decision problem of whether a given bit sequence is a valid tent code is solved in $\mathrm{O}(\log^{2} n)$ space in a sense of the smoothed complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_00327 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Smoothed Analysis of the Space Complexity of Computing a Chaotic Sequence Okada, Naoaki Kijima, Shuji Computational Complexity This work is motivated by a question whether it is possible to calculate a chaotic sequence efficiently, e.g., is it possible to get the $n$-th bit of a bit sequence generated by a chaotic map, such as $β$-expansion, tent map and logistic map in $\mathrm{o}(n)$ time/space? This paper gives an affirmative answer to the question about the space complexity of a tent map. We show that the decision problem of whether a given bit sequence is a valid tent code is solved in $\mathrm{O}(\log^{2} n)$ space in a sense of the smoothed complexity. |
| title | A Smoothed Analysis of the Space Complexity of Computing a Chaotic Sequence |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2405.00327 |