A neat footnote on function difficulty

In my last post, I argued that the difficulty of the most difficult functions in F increases in proportion to N² (where F is the set of binary functions that operate on values in [0..N-1]).

I was trying to think of a way to test this conclusion for a specific case, when I remembered an earlier post where I argued that these functions can all be represented as polynomials, as long as N is prime. This gives us a perfect test-case, because polynomials can be described as programs in the context of the previous post, where the instruction set consists of addition and multiplication.

So let's take the case where N = 23. The most complex polynomial representing a function in F will have 23² terms. In reality, the most efficient way to evaluate the function would be to preprocess x²..x²² and y²..y²². This wasn't something I accounted for in my model, but let's run with it anyway. Preprocessing would require 22 operations for x and 22 for y.

There would be 23² = 529 terms in the polynomial, and for each term we would need to perform two multiplications, so 1058 multiplications. We would need 528 additions to add the terms together.

In total, that would mean 22 + 22 + 1058 + 528 = 1630 operations would be required for the most complex function in F.

How does that compare to our prediction? For N = 23 and A = 2, the lower limit for the difficulty of functions in F would be (23² ln 23 - ln (23+2)) / (ln 4 + ln 2 + ln (23+2)) = 312.45.

So, in this test case, it seems the conclusion is right, since 1630 > 312.45. The general case for any prime N can be easily shown, where the difficulty for this particular case is d' = 2(N-1) + 3N² - 1.

The other thing that is interesting about this is that, for this particular instruction set, we can say something about the makeup of the function space in terms of difficulty. There are N^N2 functions in the set, of which (N-1)^N2 fall into the "most difficult" category. In other words, difficult functions vastly outnumber easy ones, with the ratio of "most difficult" functions to all others being 1 - ((N - 1)/N)^N2.