Amortizing or batching circuit evaluation for many different inputs?

Question

Suppose that I have a boolean function of size $k$ with $n$ inputs. I would expect to be able to evaluate it on all possible inputs in time $O(k*2^n)$ simply by calculating all the intermediate values for every possible input. Is it possible to do this faster in general, for example in time $(k+2^n)$?

In the special case of linear functions I would expect to be able to do this by going from point to point in gray code order, so that only one bit changes each time, or by calculating tables of size $1,2,4,8,\dots,2^n$ for the functions produced by holding the last $n-i$ bits at zero, using each table to calculate the next one. Are there generalizations of this for general boolean circuits, or are there proofs that no such generalizations are possible?

I have a slightly off-the-wall motivation for this. I am interested in the simulation hypothesis. One reason for running a large number of simulations would be to investigate the result of running the same scenario for all possible inputs.
I would be interested to learn that there was, or was not, a significantly more efficient approach which would achieve the same ends, especially as such a more efficient approach would not have a direct link between any particular set of simulated histories and any particular act of the program, as the increased efficiency of the program would be mean that it could not be the case that every possible history could be mapped to its own set of program activity.

Edit - batch calculation as described above is more powerful when the batch step is used inside a recursive call, as then you don't need to go through all 2^n answers at once. For #P-complete problems, each recursive call returns the number of solutions found within some range of values. For NP-complete problems, each recursive call returns whether a solution is found in some range of values.

Each recursive call uses the batch mechanism to compute the answers for 2^k different problems. This corresponds to k bits of the n bits available. So the lowest level of the recursion just looks at 2^k different results to see whether they are solutions or not, but the highest level looks at 2^k results which are each e.g. the number of solutions found within 2^(n-k) evaluations, each with the k top bits of n set to a different value. Here I assume that the language used to express our function f() is sufficiently flexible that level i+1 can treat level i as just a function f() to consider at 2^k points, even though this f() amounts to a transformation of the original f() producing a function which counts the number of solutions in a particular range or says whether this number is non-zero.

If the cost of level i+1 of the recursion is X_i+1 = b + a*X_i then for a!=1 we get X_i = a^i + b/(1 - a) and for a=1 we get X_i = ib (with variations depending on what X_0 is). Remember that the number of possible solutions examined at each level is 2^(ik) so for small a compared to 2^k this is a large speedup, and for the case of a=1 we would find that P=NP and even P=#P.

(I remain interested in answers that would firm this up or extend this)

Answer 1

Some further thoughts, at least for the case when batch generation is done by feeding a gray code or other simply generated sequence into a circuit with internal memory.

For an ordinary combinatorial logic circuit without memory, we can bound the size of a circuit needed to evaluate a general function on n bits in two ways: by providing a general construction with known size, or by observing that 2^2^n different functions require 2^2^n different circuits, so the size of the largest circuit encountered cannot be so small that there are less than 2^2^n different circuits of up to that size. Knuth Vol 4A section 7.1.2 Theorem L shows that these bounds are in fact very close together, and require a circuit of size O(2^n/n) for a general function on n bits. So combinatorial logic circuits without memory do not waste much complexity by having many different circuits computing the same function.

If we stick to the design of a gray code generator feeding a circuit with internal memory, the only source of variation is the choice of the circuit, which now includes memory elements. The description of such a circuit needs a few more bits per item to offer the possibility of memory elements, but this is just a constant factor. By the requirement that to be able to compute any of 2^2^n different functions we must provide 2^2^n different circuits, and by the observation that ordinary combinatorial logic circuits do not have staggering inefficiencies, I think we find that introducing internal memory into an otherwise pedestrian design will not allow all possible functions to be calculated using only circuits of size significantly smaller than their best combinatorial logic implementation.

(but if P=NP our simulator has other options, such as Valiant Approximate Counting, which allow them to estimate the fraction of input states leading to a particular outcome in a simulation, without actually simulating all possibilities).

I remain interested in any comments, pointers, or whatever, about anything that bears on this.