Abstract
Constraint satisfaction (CSP) and structure isomorphism (SI) are among the most wellstudied computational problems in Computer Science. While neither problem is thought to be in PTIME, much work is done on PTIME approximations to both problems. Two such historically important approximations are the kconsistency algorithm for CSP and the kWeisfeilerLeman algorithm for SI, both of which are based on propagating local partial solutions. The limitations of these algorithms are wellknown – kconsistency can solve precisely those CSPs of bounded width and kWeisfeilerLeman can only distinguish structures which differ on properties definable in C^k. In this paper, we introduce a novel sheaftheoretic approach to CSP and SI and their approximations. We show that both problems can be viewed as deciding the existence of global sections of presheaves, ℋ_k(A,B) and ℐ_k(A,B) and that the success of the kconsistency and kWeisfeilerLeman algorithms correspond to the existence of certain efficiently computable subpresheaves of these. Furthermore, building on work of Abramsky and others in quantum foundations, we show how to use Čech cohomology in ℋ_k(A,B) and ℐ_k(A,B) to detect obstructions to the existence of the desired global sections and derive new efficient cohomological algorithms extending kconsistency and kWeisfeilerLeman. We show that cohomological kconsistency can solve systems of equations over all finite rings and that cohomological WeisfeilerLeman can distinguish positive and negative instances of the CaiFürerImmerman property over several important classes of structures.
BibTeX  Entry
@InProceedings{oconghaile:LIPIcs.MFCS.2022.75,
author = {\'{O} Conghaile, Adam},
title = {{Cohomology in Constraint Satisfaction and Structure Isomorphism}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {75:175:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16873},
URN = {urn:nbn:de:0030drops168738},
doi = {10.4230/LIPIcs.MFCS.2022.75},
annote = {Keywords: constraint satisfaction problems, finite model theory, descriptive complexity, rank logic, WeisfeilerLeman algorithm, cohomology}
}
Keywords: 

constraint satisfaction problems, finite model theory, descriptive complexity, rank logic, WeisfeilerLeman algorithm, cohomology 
Collection: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) 
Issue Date: 

2022 
Date of publication: 

22.08.2022 