What is...complexity theory?

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