This weekend I have been thinking about abstract ways to measure how difficult it is to evaluate functions given a hypothetical computer with a specific instruction set.
In particular, I want to see if I can find a lower limit of difficulty for the most difficult functions of a particular type. I thought I had it nailed last night, but as soon as I went to bed I realized I was wrong.
Imagine a computer with the following properties:
1. The computer's only data type is an integer in the set [0..N-1], called an
int.
2. The computer's programs represent functions that take two
ints and returns an
int. The set of all such functions is F.
3. The computer has an instruction set composed of A <= N+2 functions drawn from F. The computer can easily evaluate every function in its instruction set.
4. The computer's programs are finite function trees, so each program has a root function drawn from the instruction set, which takes two parameters. The two parameters of the root function may be function trees, constant
ints, or the special symbols
x and
y which evaluate to the program's two input parameters. There is no recursion.
5. The difficulty of a program is the average number of operations required to evaluate the program for any possible input values
x and
y.
For simplicity, we initially assume that there is no lazy evaluation.
Given a computer like this, can we put a lower limit on the difficulty of the most difficult function in F?
If there is no lazy evaluation, then the difficulty of a function is proportional to the number of instructions. Given that there are N
N2 functions in F, if you could write maximally efficient programs to represent each of those functions, how big would the largest such efficient program need to be?
There are p
0 = N+2 distinct programs that could be written with zero instructions. These would be the programs that returned a constant value, or else
x or
y with no modification.
The number of distinct programs that can be written with one instruction is p
1 = A*(p
0 * p
0) = A(N+2)
2. That is, there are A possible instructions, which must take a program with zero instructions for each parameter.
The number of distinct programs that can be written with two instructions is p
2 = A*(p
0 * p
1 + p
1 * p
0) = 2A
2(N+2)
3. That is, the first parameter may be a zero-instruction tree, in which case the second parameter must be a 1-instruction tree, or vice-versa.
The number of distinct programs that can be written with three instructions is p
3 = A*(p
0 * p
2 + p
1 * p
1 + p
2 * p
0) = 5A
3(N+2)
4. The progression we are seeing here is that p
n = s
nA
n(N+2)
n+1, where s
n is the number of different trees that can be formed with
n binary functions.
There will be a lot of overlap in the program space, meaning there will be multiple programs that can evaluate to the same function. This means we can't say that
n instructions can always represent p
n functions, but we can say that they will represent
no more than p
n functions. Thus, for p
n = |F| = N
N2, we can be certain that the most complex program representing a function in F can be
no smaller than n instructions.
So the lower limit
d on the difficulty of the most difficult function in F is calculated as follows:
p
d > N
N2.
s
dA
d(N+2)
d+1 > N
N2.
For large values of
d, I think 3
d < s
d < 4
d. This needs to be proven, though. If it is true, we could fudge a bit and say
4
dA
d(N+2)
d+1 > N
N2.
d ln 4
+ d ln A
+ d ln (N+2) +
ln (N+2)
> N
2 ln N.
d ln 4
+ d ln A
+ d ln (N+2)
> N
2 ln N -
ln (N+2).
d > (N
2 ln N -
ln (N+2)) / (
ln 4 +
ln A
+ ln (N+2)).
Of course, there is a lot more to gnaw on here, like operation laziness and pre-evaluation, which might be real game-changers. But as we have it now, the difficulty of the most difficult functions in F increases in proportion to N2.
