Symmetries in constraint satisfaction: Weisfeiler-Leman invariance and promise problems

Abstract

This thesis focuses on the complexity of the fixed-template Constraint Satisfaction Problem (CSP) and its variants. Our contributions are two-fold. On the one hand, we study how closure of the space of CSP instances under an equivalence relation induced by the 1-dimensional Weisfeiler-Leman algorithm correlates with solvability by the Sherali-Adams hierarchy of linear programs, invariance of the template under symmetric operations, and tractability by distributed algorithms. We then extend this analysis to the more general framework of Promise Valued CSPs. On the other hand, we initiate the study of the complexity of the Promise Model Checking Problem (PMC) parametrised by the model for the existential positive and the positive fragments of first-order logic. We lay the foundations for an algebraic approach to these problems, which allows us to fully characterize the complexity of the PMC for the existential positive fragment and to give a number of upper and lower bounds for the positive fragment.

Esta tesis se centra en la complejidad del Problema de Satisfacción de Restricciones (Constraint Satisfaction Problem, CSP) de plantilla fija y sus variantes. Nuestras aportaciones se dividen en dos grupos. Por un lado, estudiamos cómo la clausura del espacio de instancias del CSP bajo una relación de equivalencia inducida por el algoritmo unidimensional de Weisfeiler-Leman se correlaciona con la resolubilidad por la jerarquía de programas lineales de Sherali-Adams, la invariabilidad de la plantilla bajo operaciones simétricas y la tratabilidad por algoritmos distribuidos. A continuación, extendemos esta análisis al marco más general de los Promise Valued CSPs. Por otro lado, iniciamos el estudio de la complejidad del Promise Model Checking Problem (PMC) parametrizado por el modelo para los fragmentos existencial positivo y positivo de la lógica de primer orden. Fijamos las bases de un enfoque algébrico para estos problemas, que nos permite caracterizar completamente la complejidad del PMC para el fragmento existencial positivo, y dar una serie de límites superiores e inferiores para el fragmento positivo.

Aquesta tesi se centra en la complexitat del Problema de Satisfacció de Restriccions (Constraint Satisfaction Problem, CSP) de plantilla fixa i les seves variants. Les nostres aportacions es divideixen en dos grups. D'una banda, estudiem com la clausura de l'espai d'instàncies del CSP sota una relació d'equivalència induïda per l'algorisme unidimensional de Weisfeiler-Leman es correlaciona amb la resolubilitat per la jerarquia de programes lineals de Sherali-Adams, la invariabilitat de la plantilla sota operacions simètriques i la tractabilitat per algorismes distribuïts. A continuació, estenem aquesta anàlisi al marc més general dels Promise Valued CSPs. D'altra banda, iniciem l'estudi de la complexitat del Promise Model Checking Problem (PMC) parametritzat pel model per als fragments existencial positiu i positiu de la lògica de primer ordre. Fixem les bases d'un enfocament algèbric per aquests problemes, que ens permet caracteritzar completament la complexitat del PMC per al fragment existencial positiu i donar una sèrie de límits superiors i inferiors per al fragment positiu.