Parameterized complexity in cognitive modeling: Foundations, applications and opportunities
Source
The Computer Journal, 51, 3, (2008), pp. 385-404ISSN
Publication type
Article / Letter to editor
Display more detailsDisplay less details
Organization
SW OZ DCC AI
Former Organization
SW OZ NICI KI
Journal title
The Computer Journal
Volume
vol. 51
Issue
iss. 3
Languages used
English (eng)
Page start
p. 385
Page end
p. 404
Subject
Cognitive artificial intelligence; DI-BCB_DCC_Theme 2: Perception, Action and ControlAbstract
In cognitive science, natural cognitive processes are generally conceptualized as computational processes: they serve to transform sensory and mental inputs into mental and action outputs. At the highest level of abstraction, computational models of cognitive processes aim at specifying the computational problem computed by the process under study. Because computational problems are realistic cognitive models only insofar as they can plausibly be computed by the human brain given its limited resources for computation, computational tractability provides a useful constraint on cognitive models. In this paper, we consider the particular benefits of the parameterized complexity framework for identifying sources of intractability in cognitive models. We review existing applications of the parameterized framework to this end in the domains of perception, action and higher cognition. We further identify important opportunities and challenges for future research. These include the development of new methods for complexity analyses specifically tailored to the reverse engineering perspective underlying cognitive science.
This item appears in the following Collection(s)
- Academic publications [238441]
- Electronic publications [122536]
- Faculty of Social Sciences [29483]
- Open Access publications [97529]
Upload full text
Use your RU credentials (u/z-number and password) to log in with SURFconext to upload a file for processing by the repository team.