PhD Proposal: Constraint SAT problems for Infinite Structures

We study the constraint satisfaction problems of selected infinite relational structures. In particular, we consider different classes of hereditarily linearly sparse graphs and their generic structures, and prove that in nice cases, the constraint satisfaction problems of the generic structures have simple finite characterizations and are therefore NP-complete. We also study the CSP of unary expansions of directed graphs. When we expand the simple structure (Z,succ) with one unary predicate U, its CSP (Constraint Satisfaction Problem) may vary in complexity. We find some sufficient conditions for its tractability, prove bounds on its complexity, and then generalize our results to more complicated structures. Concurrently, we give a Karp-equivalent characterization of CSP(Z,succ, U)’s.Examining Committee:

Chair:Co-Chair:Department Representative:

Dr. William Gasarch Dr. Chris LaskowskiDr. Rob Patro