Cognition and Complexity
Course infoSchedule
Course moduleSOW-MKI40
Credits (ECTS)6
Language of instructionEnglish
Offered byRadboud University; Faculty of Social Sciences; Artificial Intelligence;
N. Donselaar, MSc
Other course modules lecturer
Contactperson for the course
N. Donselaar, MSc
Other course modules lecturer
N. Donselaar, MSc
Other course modules lecturer
prof. dr. I.J.E.I. van Rooij
Other course modules lecturer
prof. dr. I.J.E.I. van Rooij
Other course modules lecturer
Academic year2020
SEM2  (25/01/2021 to 16/07/2021)
Starting block
Course mode
Registration using OSIRISYes
Course open to students from other facultiesYes
Waiting listNo
Placement procedure-
In this course, students learn to use methods derived from computational complexity theory for analyzing the (in)tractability of cognitive models, and for identifying sources of complexity in a model. Students also learn how this knowledge can be used to make model revisions that yield tractability. As two competing models may differ in the nature of their sources of complexity, the analyses can also yield novel empirical predictions that can be used to test the models.
The functioning of the human brain can be studied and modeled at different levels of abstraction ranging from the neural implementation level to a cognitive computational level. Ideally, models postulated at the computational level are consistent with the brain resources available at the neural level. Building computational models that fit with human brain resources can be quite challenging. This is illustrated by the fact that many computational models in Cognitive (Neuro)science postulate cognitive computations that are - on closer inspection - computationally intractable. Here ‘computational intractability' means that the postulated computations require more resources (such as time, space, memory, hardware) than a human mind/brain or any computational mechanism has realistically available.
Examples of intractable computational models can be found in almost all cognitive domains, including perception, learning, language, planning, decision-making, communication, and reasoning. Intractability makes these models psychologically and neurally implausible as cognitive computational level models of brain functioning. However, there are ways to deal with this problem by identifying sources of complexity in these models and investigating if they can be removed from the model without the loss of explanatory power. This course covers several concepts and techniques that can be used to this end.
Presumed foreknowledge
A completed (academic) BSc degree in Artificial Intelligence or related field (such as Cognitive Science, Computing Science, Cognitive Psychology, Cognitive Neuroscience, Philosophy, or Linguistics). Furthermore, the course assumes that students have some affinity with cognitive psychological research, some proficiency in algorithm design and analysis.
Test information
- Take-home assignment 1 (35%) - Take-home assignment 2 (35%) - Paper/commentary (30%) The weighted average of all grading parts should be sufficient to pass the course.
The course is a 6EC semester course. The first part of the course serves to introduce the conceptual framework of computational complexity analysis and its associated techniques (+/-8 lectures) and illustrates the application of these techniques to existing cognitive models (+/-3 lectures). During lectures and in take-home assignments students will have ample opportunity to practice the techniques. In the second part of the course (4-5 weeks) students perform an individual project: write a scientific commentary using the knowledge that they developed during the course. 
Required materials
Literature list
Selected readings (book chapters + original articles)
Course guide
Course manual

Instructional modes
Attendance MandatoryYes

Individual projects
Attendance MandatoryYes

Attendance MandatoryYes

Attendance MandatoryYes

Take home assignment 1
Test weight35
Test typeAssignment
OpportunitiesBlock SEM2, Block SEM2

Take home assignment 2
Test weight35
Test typeAssignment
OpportunitiesBlock SEM2, Block SEM2

Test weight30
Test typePaper
OpportunitiesBlock SEM2, Block SEM2