(You can watch the video version of this post on YouTube.) Now a lot of the time, the way that NP-hard problems get talked about is as if you can’t solve them. Well, probably not in worst-case polynomial time on a deterministic Turing machine - sure, but exponential time is not like .. forbidden, it’s just: a lot. Computers are pretty fast though and sometimes the instances that you want to solve aren’t that large anyway.…

(You can watch the video version of this post on YouTube.) Now if you study computer science, you take a databases class, right? I guess there are trends and there are different ways to focus it, but still everybody learns SQL. SELECT, FROM, WHERE, GROUP BY, HAVING. Nested queries are also commonly taught, I assume. Then you get things like UNION and INTERSECT, ALL and ANY, IN and NOT IN.…

(You can watch the video version of this post on YouTube.) Now there are all kinds of different complexity classes for, uh, probabilistic computation. We’ll get into some reasonable ones another time, but here’s one that sounds - like a good idea, maybe, but is really powerful in a way that’s just not reasonable. So PP is the class of problems that can be solved in Probabilistic Polynomial time in the sense that we must accept YES instances with probability strictly larger than $\frac12$ and and No instances with probability at most $\frac12$.…

(You can watch the video version of this post on YouTube.) Hello there, I’m Thomas and I’m a computer scientist. When I was a first year student in Utrecht, we had a mandatory maths course, “Maths for Computer Scientists,” and .. I don’t even know what was in there anymore; I forgot most of it soon after the exam, I guess. And people did complain like: why do I need to learn this?…