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.
|Betreuer:in / Berater:in|
|Datum der Verteidigung (Datum der Urkunde)||3 Apr. 2023|
|Publikationsstatus||Veröffentlicht - 2023|
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.Thesis