Observables are glocal

We show that the problem of observables can be fully resolved for background independent theories defined on graphs, through the explicit construction of complete observables. The appropriate analogue of coordinate independence is argued to be the invariance under changes of graph labels, a kind of permutation invariance. Invariants are formed by group averaging and they probe the entire graph -- they are global. Strikingly, sets of complete observables can be constructed so that each of the invariants comprising them seeks a connected subgraph structure -- local correlations. Geometrical information is fully encoded through this subtle interplay of global and local graph notions, a behavior we term glocal. This provides physically meaningful complete sets of observables for discrete general relativity, and a permutation invariant reformulation of the spin networks state space of loop quantum gravity. Our analysis reveals an important new aspect of the problem of observables, demonstrating a deep connection between the theory of spacetime and computational complexity theory: the construction of a complete set of observables for discrete spacetime theories is computationally costly, as it corresponds to solving a graph isomorphism problem.