2024/05/01 by Okada, Naoaki, Kijima, Shuji
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2405.00327
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(log2 n) space in a sense of the smoothed complexity.