Intractability and approximation of optimization theories of cognition

Many computational- or rational-level theories of human cognition suffer from computational intractability: the postulated optimization functions are impossible to compute in a reasonable time by a finite mind/brain, or any other computational mechanism. It has been proposed that such intractable theories can nevertheless have explanatory force if we assume that human cognitive processes somehow approximate the optimal function. This raises the question of when a cognitive process can be said to approximate an optimal function. In this paper, we distinguish between two notions of approximation, called value-approximation and structure-approximation respectively, and show that they are not equivalent. Although a mathematical framework for assessing degrees of tractable value-approximability has long been available, no such framework previously existed for structure-approximability. In this paper, we present a framework consisting of definitions and proof techniques for assessing degrees of structure-approximability. We illustrate the use of our framework for a particular intractable cognitive theory, i.e., Thagard and Verbeurgt’s (1998) Coherence model, known to be equivalent to harmony maximization in Hopfield networks. We discuss implications of our findings for this class of theories, as well as explain how similar results may be derived for other intractable optimization theories of cognition.

► We consider optimization theories of cognition that are intractable.
► We study how approximation can dissolve intractability.
► We introduce a new approximation notion relevant for cognitive science.
► We present proof techniques for assessing approximability.