A lower bound on computational complexity given by revelation mechanisms (*)

This paper establishes a lower bound on the computational complexity of smooth functions between smooth manifolds. It generalizes one for finite (Boolean) functions obtained (by Arbib and Spira [2]) by counting variables. Instead of a counting procedure, which cannot be used in the infinite case, the dimension of the message space of a certain type of revelation mechanism provides the bound. It also provides an intrinsic measure of the number of variables on which the function depends. This measure also gives a lower bound on computational costs associated with realizing or implementing the function by a decentralized mechanism, or by a game form. <!--ID="" Correspondence to: S. Reiter-->