The Art Gallery Problem (AGP) is a classic problem in computational geometry, introduced in 1973 by Victor Klee. Given a simple polygon P and an integer k, the goal is to decide if there exists a set G of k guards within P such that every point p E P is seen by at least one guard g E G. Each guard corresponds to a point in the polygon P, and we say that a guard g sees a point p if the line segment pg is contained in P. We prove that the AGP is 3R-complete, implying that (1) any system of polynomial equations over the real numbers can be encoded as an instance of the AGP, and (2) the AGP is not in the complexity class NP unless NP = 3R. As a corollary of our construction, we prove that for any real algebraic number alpha, there is an instance of the AGP where one of the coordinates of the guards equals alpha in any guard set of minimum cardinality. That rules out many natural geometric approaches to the problem, as it shows that any approach based on constructing a finite set of candidate points for placing guards has to include points with coordinates being roots of polynomials with arbitrary degree. As an illustration of our techniques, we show that for every compact semi-algebraic set S subset of [0, 1](2), there exists a polygon with corners at rational coordinates such that for every p is an element of [0,1](2), there is a set of guards of minimum cardinality containing p if and only if p is an element of S. In the 3R-hardness proof for the AGP, we introduce a new 3R-complete problem ETR-INV. We believe that this problem is of independent interest, as it has already been used to obtain 3R-hardness proofs for other problems.
