UCLA

We explore the descriptive set theory of problems originating in theoretical computer science. We investigate a few special cases of locally checkable labelling problems using a variety of Borel and measurable techniques. Our result clarifies a small part of the connection between descriptive set theory and distributed computing. And, we adapt tools from the algebraic approach to constraint satisfaction problems to the Borel setting. In particular we draw a direct connection between NP-completeness and $\mathbf{\Sigma}^1_2$-completeness.