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 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 O(log² n) space in a sense of the smoothed complexity.
No takes yet. Share an insight, caveat, or question.
Okada et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: