A simple observation regarding iterations of finite-valued polynomial-time functions. (English) Zbl 1174.03017

For any map \(f:\mathbb{N}\to\mathbb{N}\), let its iteration be definded by \(\text{It}(f):(n,x)\mapsto f^n(x)\) (superscript denotes map composition). Let PF be the class of maps that are (Turing) computable in polynomial time. It is shown in the paper that whenever \(f\) is in PF and has a finite image, then \(\text{It}(f)\) falls also in the class PF.
The author also shows that when considering primitive recursion, the collection of maps in PF with finite image fails to be closed under the general assumptions \(\text{P}\not= \text{NP}\) and \(\text{P} \not= \text{PSPACE}\). Namely, the satisfiability problem for quantified Boolean formulae is PSPACE-complete and the knapsack problem is NP-complete. Under codings done in PF their characteristic functions can be obtained through primitive recursion using maps with finite images.
Finally, the author poses two interesting questions: Is it true that any map in PF is periodic up to the addition of a polynomial? Is it true that any periodic map in PF is the iteration of a map with finite image? In case of positive answers, any map in the class PF would be the addition of a polynomial and the iteration of a map with finite image.
The paper consists of a simple remark, as the author himself claims, and it provides an interesting closure property of polynomial-time computable maps.


03D20 Recursive functions and relations, subrecursive hierarchies
03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity