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

Autor/a

Butti, Silvia

Director/a

Dalmau, Víctor

Data de defensa

2022-10-20

Pàgines

203 p.



Departament/Institut

Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions

Programa de doctorat

Programa de doctorat en Tecnologies de la Informació i les Comunicacions

Resum

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.

Paraules clau

Constraint satisfaction problems; Linear programming; Weisfeiler-Leman algorithm; Sherali-Adams hierarchy; Distributed algorithms; Model checking; Problema de satisfacción de restricciones; Programación lineal; Algoritmo de Weisfeiler-Leman; Jerarquía de Sherali-Adams; Algoritmos distribuidos; Verificación de modelos; Problema de satisfacció de restriccions; Programació lineal; Algoritme de Weisfeiler-Leman; Jerarquia de Sherali-Adams; Algorismes distribuïts; Verificació de models

Matèries

62 - Enginyeria. Tecnologia

Documents

tsb.pdf

1.475Mb

 

Drets

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-sa/4.0/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-sa/4.0/

Aquest element apareix en la col·lecció o col·leccions següent(s)