# If a Ptime function loses x bits of data at every call, is it a one way function?

If we have a computational function $f(x)=g(f(x-1)^2)$, where $g(y)$ is a floating point operation, mapped onto a given number of bits say 32 bits (thus leading to loss of a given number of precision bits every time), is the function a one-way function?

• It might just be that I know nothing about one-way functions but I can't work out what you're asking. In the context of computability, "recursive" and "computable" mean the same thing; in the context of programming, I don't see how the function being recursive (i.e., calling itself) is relevant. The title says the function is in P but the question body doesn't. What does it mean for a function to be "mapped onto a fixed size string system"? "With less predictability" than what? – David Richerby Sep 25 '15 at 9:38
• We don't know if one-way functions exist at all. A function that maps to a finite domain is definitely not one-way, though. – Tom van der Zanden Sep 25 '15 at 9:47

A one-way function is a function which is easy to compute but hard to invert. More accurate, it is a polytime function $f$ such that given a random $y$, it is hard to find a preimage $x$ satisfying $f(x) = y$. The exact sense of hardness isn't important here.
Your function is not one-way since it fails the first requirement: it is not easy to compute. If you use your recursive definition, computing $f(x)$ takes $x$ applications of the function $g$, which is exponential time.