tvd pod

When we talk about an optimisation problem, there are actually different variants that we’re not usually explicit about: decision, optimisation, and construction. We don’t usually care that much about this distinction - it’s just that algorithms usually solve the construction version and complexity theory is usually about the decision version, where we don’t mind because typically it’s all polynomially related. But we can still be smart about it...

More pedantry about NP-hardness! We have already seen a version of the SUM OF RADICALS problem, where it turned out comparing sums of square roots is tricky. But irrational numbers are kind of wild, right, so maybe we don't really need to care? Surprise: geometry! Euclidean distance has square roots so this is kind of a big deal, actually, and it bites both ways for NP-completeness.

We have talked about "reasonable encodings" of integers, and why that matters, but what about real numbers? You could give a finite expansion, that is fine, or use rational numbers - though in either case you might have to be a little bit careful about how large your representation is and if you can actually work with that representation efficiently. Queue the Sum of Radicals problem.

Question: How do you efficiently encode an arbitrarily large integer using bits? And to make things interesting, let’s say I can’t see how long your encoding is. I just start reading and that must tell me when I’m done reading; otherwise you could just write it in binary and we’d be done.

There is a property of matrices called “unimodularity” and a variant I want to talk about today called total unimodularity. The definition is a bit opaque: a matrix is totally unimodular if every square submatrix has determinant 0, +1 or −1. That may not be the most intuitive thing, but it turns out totally unimodular matrices have some algorithmically useful properties.

As theorems go, the Intermediate Value Theorem is pretty obvious, especially if you don't try to generalize it. But asw a tactical move, it is useful to be aware of.

NP-hardness is about Turing machines. It’s about symbols on tapes, and state transitions, and moving heads. There are shortcuts to thinking about this that are basically equivalent in all the ways that we care about, but here’s a formal “implementation detail” – so to speak – that leaks out of the definition: so-called reasonable encodings.

There are all kinds of different complexity classes for 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.

If you study computer science, you take a databases class. I guess there are trends and there are different ways to focus it, but still everybody learns SQL. Maybe you’ll say “oh of course, didn’t you know that?” But here are some things that I didn’t know until fairly recently. If there is a thing you wish you were allowed to write, maybe you actually are!

NP-hard problems often 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 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. Depending on both the problem and the methods, you can solve larger instances than you might expect.