# Amortizing or batching circuit evaluation for many different inputs?

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)

• What precisely do you mean by "size k"? – mhum May 13 '16 at 0:03
• @mhum the size of the representation of the function provided to the algorithm, for example if the function is presented as a boolean circuit, the size of the data-structure that describes the circuit. – mcdowella May 13 '16 at 4:23
• Hm. It may be worth distinguishing between the size of the representation and the time it takes to evaluate the function. For example, if the function is provided as a truth table, we would expect the size to be exponential in $n$ but the time to evaluate to be constant. – mhum May 16 '16 at 19:08
• Possible relevant: cstheory.stackexchange.com/q/36389/5038 – D.W. Jan 3 '17 at 7:07