Here, I compile a set of videos that complement a course on computational complexity for cognitive scientists that I co-teach with Nils Donselaar. We use the textbook Cognition and Intractability, that I co-authored with Mark Blokpoel, Johan Kwisthout, and Todd Wareham. Chapter 1 is freely available here.

Why care about computational complexity?

This video is of a brief talk at the Learning Salon, explaining why cognitive scientists should care about computational complexity. See Chapters 1 and 9 of our textbook for more information.

Time-complexity and big O

This video explains the ideas behind time-complexity of algorithms and big O notation.

P versus NP

These two videos explain the P vs. NP question

Polynomial-time problems and algorithms

This video explains the class P, problems solvable in polynomial time.

A brief explanation of how to solve Minimum Spanning Tree problem.

This video explains two polynomial-time algorithms for solving Minimum Spanning Tree.

P, NP and NP-completeness

The below videos explains NP-completeness.

This is a full lecture on P, NP, and NP-completeness by Erik Demaine.

Polynomial time reductions and NP-hardness

This video explains what makes a problem NP-hard and how this can be proven using polynomial-time reduction.

This video explains Karp reductions (which in the textbook are also referred to as many-one polynomial-time reductions).

Parameterized complexity

This video presents a full lecture on fixed-parameter algorithms.

Extras

Here follow 2 videos in which we apply computational complexity analysis to study the hardness of cognitive science and creating human-level/-like AI.