Two Measures of Difficulty

This paper addresses the measurement of difficulty for functions defined over discrete domains and demonstrates how formalizing notions of difficulty can improve our understanding of economic phenomena. The principal aims of this paper are fourfold: to introduce two measures of difficulty for functions defined over several discrete variables, to employ these measures to explain the performance of search algorithms, to contrast these measures with existing measures of difficulty, and, finally, to (preliminarily) apply these measures to an economic problem, the organizational structure of firms. We have selected this application because of its inherent difficulty and because it has not proven tractable using standard techniques. Though much of this work relies on the formal statement and proof of claims, a significant portion consists of computational experiments, particularly when we are explaining the performance of search algorithms and comparing measures of difficulty.