The decision version of the Art Gallery Problem asks, for a given polygon P and integer k, whether P can be guarded by k points. In other words, can P be covered by the visibility regions of at most k points in P? A set C (of any size) is called a candidate set for (P,k) when, if G can be guarded by k points, it can be guarded by k points in C. I will show that it is not possible for an algorithm to produce a subexponential-sized candidate set in subexponential time unless the Exponential Time Hypothesis fails.

This is joint work with Tillmann Miltzow.