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 proves 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.
Year of publication: |
1996
|
---|---|
Authors: | Mount, Kenneth R ; Reiter, Stanley |
Published in: |
Economic Theory. - Springer. - Vol. 7.1996, 2, p. 237-66
|
Publisher: |
Springer |
Saved in:
Saved in favorites
Similar items by person
-
Information and Performance in the (New)2 Welfare Economics.
Reiter, Stanley, (1977)
-
The Knowledge Revealed by an Allocation Process and the Informational Size of the Message Space
Reiter, Stanley, (1973)
-
Coordination of Economic Activity: An Example
Reiter, Stanley, (1999)
- More ...