2
$\begingroup$

I have a deterministic function $f(x_1, x_2, ..., x_n)$ that takes $n$ arguments.

Given a set of arguments $X = (x_i)$, I can compute $U_X = \{ i \in [1, n] : x_i \text{ was read during the evaluation of } f(X) \}$

Would it be valid to use the set $K_X = \{(i, x_i): i \in U_X\}$ as a memoization key for $f(X)$?

In particular, I am worried that there may exist $X=(x_i)$ and $Y=(y_i)$ such that:

$$ \tag1 U_X \subset U_Y $$ $$ \tag2 \forall i \in U_X, x_i = y_i $$ $$ \tag3 f(X) \neq f(Y) $$

In my case, the consequence of the existence of such $X$ and $Y$ would be that $K_X$ would be used as a memoization key for $f(Y)$, and would thus return the wrong result.

My intuition says that, with $f$ being a deterministic function of its arguments, there should not even exist $X$ and $Y$ (with $U_X$ a strict subset of $U_Y$) such that both $(1)$ and $(2)$ hold (much less all three!), but I would like a demonstration of it (and, if it turns out to be trivial, at least pointers to the formalism that makes it trivial).

$\endgroup$
3
$\begingroup$

As long as $f$ is deterministic and depends only on its arguments (not on other global variables), yes, you can safely use that as a memoization key. The bad case cannot happen.

You can see this by thinking about what happens as it reads the $t$th argument and using induction on $t$. Let $i_1,i_2,i_3,\dots,i_t$ be the sequence of argument indices read (i.e., $f$ first reads $i_1$ when running on input $x$, then reads $i_2$, etc.). For each $t$, if $f(x)$ and $f(y)$ have behaved the same up until just before they read the $t$th of these, then the next index examined by $f(x)$ and $f(y)$ will be the same, say $i_t$; if additionally $x_{i_t} = y_{i_t}$, then it follows $f(x)$ and $f(y)$ will behave the same up until just before they read the $t+1$st of their arguments. Since $i_t \in U_X$, $x_{i_t} = y_{i_t}$ is guaranteed by your assumptions. Now use induction.

This assumes everything is deterministic. For instance, $f$ had better not be allowed to read a random-number generator, the current time of day, or other global variables. Beware that on some platforms there can be surprising sources of non-determinism, e.g., due to aspects of behavior that are unspecified and might depend on external factors. For instance, I have a recollection that floating-point math in Java can introduce non-determinism in some cases, and so if you want to write code that is verifiably deterministic, you probably want to avoid all floating-point math.

$\endgroup$
2
$\begingroup$

You can simulate $f$ by what is known in complexity theory as a decision tree. Each node is labelled by an input $x_i$, and the edges going downwards are labelled by the possible values of $x_i$. Leaves are labelled by the output of $f$. For decision trees you can prove your claim by induction on the height of the decision tree.

This reduces what you want to show to fleshing out the claim that $f$ can be simulated by a decision tree. If you have a computing formalism then you can prove this by induction on the length of the program, but we don't normally do that in complexity theory. We just spend a few seconds thinking about the matter, and see that the claim is obvious, and go on with our life.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.