Symposium on

Computational Complexity Analyses of Cognitive Models

to be held at the 2006 Annual Meeting of the

Society for Mathematical Psychology (SMP2006),

Vancouver, 30 July-1 August, 2006.

1. Computational Complexity Analyses of Cognitive Models [Symposium Introduction]

Iris van Rooij and Itiel E. Dror

Computational-level analyses are often considered biologically unmotivated or irrelevant. However, such analyses can help identify theoretical constraints that must be met if we are to really understand human cognition, including if and how it can, in principle, be supported by a system like the human brain. This symposium focuses on the theoretical constraint that the brain has limited computational resources. This means that models of cognition are realistic only so far as they assume no more computational resources than the brain has available.

The critical question is whether it is possible, and if so how, to assess the computational resource requirements of cognitive models? It has been argued that we can get lower bounds on the resources consumed by computational-level models by drawing on the theory of computational complexity and its associated methods for inter-model reduction.

With this symposium we wish to address the following questions: Can computational resource requirements of cognitive models be assessed independently from models of brain architecture? Can computational complexity analyses of cognitive models inform models of brain architecture? Can models of brain architecture inform computational complexity analyses of cognitive models? In this symposium we put forward that the answer is 'yes' to all three questions. The contributors will illustrate these answers by presenting relevant ideas and insights from different cognitive domains.

2. A Complexity Level Analysis of Vision: 15 years Later

John Tsotsos

The goal is to provide a theoretical foundation for the architecture and processing of visual information in the human brain. More to the point, a theoretical justification is sought for why biological vision must include attention as a basic functionality and what form does an attentive mechanism take. Since past discussions of attention always seem to involve claims of resource limitations, it is natural to look to computational complexity to see if any insights may be gained. The theory of NP-completeness is used to assess the feasibility of Visual Search, a common attentive task that is a ubiquitous functionality in biological vision. Since this problem is shown to require exponential time in its most general formulation, the brain cannot be solving this problem and instead approximations are required that re-shape this general problem so that it can be solved by the brain. In turn these implementation independent considerations constrain the kinds of mechanisms that can be implemented using neural or computer machinery and have led to a theory of visual attention with significant predictive power. This overall development will be briefly over viewed with several of the predictions that have now received significant evidence described.

3. Neurocomputational Resources and Network Optimization

Christopher Cherniak

A bounded-resource perspective on theories in mind / brain science is by now familiar. Awareness of limitations on available resources usefully constrains models at levels of abstract operations, software, and hardware. This discussion focusses upon brain-wiring. A paradox has recently emerged: Available neural connectivity in, e.g., cerebrum, is stringently limited, yet deployment of interconnections shows very finegrained optimization. Network optimization -- rather than just network satisficing -- applies well to neuroconnectivity architecture. Such layout cost-minimization problems are a major hurdle of microcircuit design, and are known to be NP-complete. How are they effectively solved in biology?

4. Assessing Theories of Language Processing using Parameterized Complexity

Todd Wareham

Many computationally-oriented theories for natural language processing (NLP) have been proposed over the last 50 years. A fundamental stumbling block to both implementing these theories in practical NLP systems and formulating biologically realistic versions of these theories is isolating the mechanisms responsible for computational infeasibility in such a theory. It has been shown how this can be done using classical complexity analysis. I will describe how these methods can be improved by using parameterized complexity, with particular reference to analyses of various theories of finite-state phonological processing.

5. Computing Maximum Coherence: A Hard Nut to Crack?

Ulrike Stege and Iris van Rooij

Maintaining a coherent belief system can be difficult. Explaining how people do it can be even harder. Many models of belief fixation run into the problem of computational intractability. This is also the case for the Coherence model put forth by Paul Thagard; the model has been proven NP-hard. In this talk we reconsider Thagard's Coherence model from a parameterized complexity perspective. In particular, we analyze the complexity of computing the Coherence problem when parameterized by c (the number of satisfied constraints) and i (the number of unsatisfied constraints). We prove that the problem is fixed-parameter tractable for both parameters. This result presents us with a paradox: Computing a maximally coherent belief system is easy for both low levels and high levels of coherence in belief networks. Does this mean that Coherence is not so hard to compute after all?