Constraint Network Satisfaction for Finite Relation Algebras

Research output: Types of ThesisDoctoral thesis

Contributors

Abstract

Network Satisfaction Problems (NSPs) are computational decision problems, studied intensively since the 1990s. The major open research challenge in this field is to understand which of these problems are solvable by polynomial-time algorithms. We provide a full complexity classification of symmetric NSPs with a flexible atom; all problems in this class are in P or NP-complete. This result was obtained by using a connection to infinite-domain Constraint Satisfaction Problems (CSPs), a Ramsey-type result by Hubička and Nešetřil and Bulatov’s dichotomy theorem for conservative finite structures. The talk introduces the studied subclass of NSPs, explains the connection to CSPs and presents the main ideas of the classification proof.

Details

Original languageEnglish
Supervisors/Advisors
Defense Date (Date of certificate)3 Apr 2023
Publication statusPublished - 2023
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.Thesis

Keywords