Complexity of Constraint Satisfaction Problems for Unions of Theories

Johannes Greiner

AutorIn

Johannes Greiner

Titel

Complexity of Constraint Satisfaction Problems for Unions of Theories

Zitierfähige Url:

https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-773158

Erstveröffentlichung

2022

Datum der Einreichung

06.07.2021

Datum der Verteidigung

08.12.2021

Abstract (EN)

Constraint Satisfaction Problems (CSPs) are a class of decision problems where one usually fixes a structure A and seeks to decide whether or not a given conjunction of atomic formulas is satisfiable in A or not. It has been shown by Bodirsky and Grohe that every computational decision problem is equivalent to some CSP via a polynomial-time Turing reduction. For structures A with finite domain Zhuk and Bulatov both proved an algebraic criterion classifying in which cases the CSP of A is in P and when it is NP-hard. For some classes of structures with infinite domain, there are similar P vs NP-hard dichotomies. This thesis continues the latter line of research for CSPs of first-order theories. In this version of CSPs, a theory is fixed and one seeks to decide whether or not a given conjunction of atomic formulas is satisfiable in some model of T. Assuming that the CSPs of theories T1 and T2 are polynomial-time tractable, we prove necessary and sufficient conditions for polynomial-time tractability of the union of T1 and T2. For some classes of theories, P vs NP-hard dichotomies are proven. To achieve this, various 'combinations' of structures are examined, a technique called 'sampling' is generalized to theories and clones of polymorphisms of temporal structures are examined in detail.

Freie Schlagwörter (DE)

Entscheidungsprobleme, Temporale Strukturen, Komplexität, Kombination von Strukturen

Freie Schlagwörter (EN)

constraint satisfaction, temporal structure, complexity, combination of structures

Klassifikation (DDC)

510

Klassifikation (RVK)

SK 200

GutachterIn