A LOWER-BOUND ON COMPUTATIONAL-COMPLEXITY GIVEN BY REVELATION MECHANISMS

This paper establishes a lower bound on the computational complexity o f smooth functions between smooth manifolds. It generalizes one for fi nite (Boolean) functions obtained (by Arbib and Spira [2]) by counting variables. Instead of a counting procedure, which cannot be used in t he infinite case, the dimension of the message space of a certain type of revelation mechanism provides the bound. It also provides an intri nsic measure of the number of variables on which the function depends. This measure also gives a lower bound on computational costs associat ed with realizing or implementing the function by a decentralized mech anism, or by a game form.