Existential Theory of the Reals

(You can watch the video version of this post on YouTube.)

Now I’m aware I already have a number of posts on here being pedantic about NP-hardness and, uh, let’s do another one of those! We’ve alreay 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 that shouldn’t really be a surprise and surely it’s a bit of a niche concern: irrational numbers? Surprise: geometry! Euclidean distance has square roots so this is kind of a big deal, actually, and it bites both ways for NP-completeness; I’ll give two examples.

I was working on some problem and it had weights that, realistically, should come from Euclidean distances. With arbitrary integer weights, an NP-hardness proof was fairly easy, but in order to get those weights from a set of points in space, I ended up giving some of them irrational coordinate values. So if you forget about having to write it on a Turing-machine tape, the first proof works. But it doesn’t, of course, because – repeat after me – NP-hardness is about Turing machines. So I showed that you could round the coordinates to a particular precision and all the properties I needed for the reduction to work were still true. So then, but only then, had I shown NP-hardness.

In addition to screwing with hardness, real numbers can also mess with membership in NP. One way to think about NP is the existence of a polynomial-size certificate that can be checked in polynomial time, and often that’s how you would think about showing membership in NP.

Consider unit disc graphs, which are the intersection graphs of sets of unit discs in the plane. Their recognition (or: realisability) problem is this: given a combinatorial description of a graph $G$, is this a unit disc graph? That is, does there exist a set of unit discs whose intersection graph is $G$? That may sound like surely it’s in NP, since we can certify it with (for example) the $n$ centres of the discs. But wait: how are we going to encode this? How precise do we need to be? It has been shown, actually, that there exist unit disc graphs where, if you’re going to explicitly write the actual coordinates, you need exponential precision. So that’s not a valid certificate for showing membership in NP! The precise situation is a bit tricky, but you can look up the details if you need to.

Or we could bite the bullet and say that we are fine with real numbers in the certificate (and update the model of computation accordingly) and then we get a complexity class called Existential Theory of the Reals: “existential” in the sense of quantification, like “there exist real numbers such that …” The unit disc graph recognition problem is actually complete for the class.