Understanding Complexity Theory: Key Concepts & Theorems 🧠

Goal.
I would like to tell you a bit about my favorite subfields of mathematics (in no particular order), highlighting key theorems, ideas or concepts and why I like them so much. This is a variation of “My favorite theorems” and I park the videos on that list as well.

This time.
What is...complexity theory? Or: Subfields of mathematics 19.

Disclaimer.
Nobody is perfect, and I might have said something silly. If there is any doubt, then please check the references.

Slides.
http://www.dtubbenhauer.com/youtube.html

TeX files for the presentation.
https://github.com/dtubbenhauer/My-TeX-files

Thumbnail.
https://en.wikipedia.org/wiki/NP_(complexity)#/media/File:P_np_np-complete_np-hard.svg

Main discussion.
https://en.wikipedia.org/wiki/Computational_complexity_theory
https://en.wikipedia.org/wiki/Computational_complexity
https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
https://complexityzoo.net/Complexity_Dojo/Cook-Levin_Theorem
https://annals.math.princeton.edu/2021/193-2/p04

Background material.
https://en.wikipedia.org/wiki/Algorithm
https://en.wikipedia.org/wiki/List_of_complexity_classes
https://en.wikipedia.org/wiki/Analysis_of_algorithms
https://en.wikipedia.org/wiki/Worst-case_complexity
https://en.wikipedia.org/wiki/Average-case_complexity
https://en.wikipedia.org/wiki/Time_complexity
https://en.wikipedia.org/wiki/Space_complexity

Computer talk.
https://complexityzoo.net/Complexity_Zoo
https://gmplib.org/manual/Multiplication-Algorithms#Multiplication%20Algorithms
https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm#Implementation_details

Pictures used.
https://en.wikipedia.org/wiki/Algorithm#/media/File:GCD_through_successive_subtractions.svg
https://cdn.hashnode.com/res/hashnode/image/upload/v1606567598755/dVUd0j4A5.png?auto=compress,format&format=webp
https://www.codeandgadgets.com/wp-content/uploads/2017/06/karatsuba-featured-image.gif
Picture created using https://reference.wolfram.com/language/ref/Plot.html
Picture from https://annals.math.princeton.edu/2021/193-2/p04
https://en.wikipedia.org/wiki/NP-completeness#/media/File:P_np_np-complete_np-hard.svg
https://upload.wikimedia.org/wikipedia/commons/thumb/8/89/Relative_NPC_chart.svg/1280px-Relative_NPC_chart.svg.png

YouTube and co.
https://www.youtube.com/watch?v=W9G_1xG77LE
https://www.youtube.com/watch?v=LW_37i96htQ
https://www.youtube.com/watch?v=6Az1gtDRaAU

#logic
#computerscience
#mathematics