For instance, A function that is computable but not invertable in log space, Is it one-way function?
What are the known definitions of one-way functions? (especially the ones that do not invoke polynomials)
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityUsually one-way functions are used for crypto, and so you want that no efficient adversary can invert the function. Identifying efficient adversaries with randomized polynomial-time, you get the typical notion of security which talks of randomized poly-time machines. But of course you can think of different security notions.
For super-fast crypto, you may want the one-way function to be computable in restricted models. Here a great result by Applebaum, Ishai, and Kushilevitz shows that a poly-time computable OWF implies a OWF where each output bit depends on just O(1) input bits (which is arguably one of the simplest computational models you can think of).
Let me start with traditional definition of one-way function (with polynomials):
A function '$f: {0, 1}^* \rightarrow {0, 1}^*$' is one-way if f can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm A,
$Pr[f(A(f(x))) = f(x)] < \frac{1}{p(n)}$
for every polynomial p(n) and sufficiently large n, assuming that x is chosen from the uniform distribution on ${0, 1}^n$ and the randomness of A.