Skip to main content
eScholarship
Open Access Publications from the University of California

UCLA

UCLA Electronic Theses and Dissertations bannerUCLA

Descriptive Aspects of Locally Ckecable LAbelling and Constraint Satisfaction Problems

  • Author(s): Thornton, Riley
  • Advisor(s): Marks, Andrew S.
  • et al.
Abstract

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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View