The Relevance of Parameterized Computational Complexity Theory to Cognitive Modeling

ffl In order to evaluate the utility of a measure M of the power of cognitive models, it is useful to answer the following questions: (1) What is M? (2) Why is M a good measure of the power of a model? (3) What is the power of a model under M? (4) How does one measure the power of a model under M? (5) What are the sources of power in a model under M? (6) How does one isolate the sources of this power? ffl Focus on computational complexity as a measure of model power. ffl Within this framework, the recently developed theory of parameterized computational complexity [4] can be used to isolate the sources of model power. ffl This discussion is illustrated by an analysis of the sources of power in Declarative Phonology [7], a constraint-based model in linguistics. What is computational complexity? ffl A (computational) problem P is a relation between inputs and outputs; an algorithm A for P is a set of instructions relative to some computer which, for any input of P , computes..