Constraint Network Satisfaction for Finite Relation Algebras
Research output: Types of Thesis › Doctoral 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 language | English |
---|---|
Supervisors/Advisors |
|
Defense Date (Date of certificate) | 3 Apr 2023 |
Publication status | Published - 2023 |
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.Thesis