Omega-categorical sandwiches for promise constraint satisfaction problems

Abstract

Etwa zu der Zeit, als die Dichotomie-Vermutung für Bedingungserfüllungsprobleme (engl. Constraint Satisfaction Problems; CSPs) von Bulatov und Zhuk im Jahr 2017 unabhängig bewiesen wurde, zog eine Verallgemeinerung von CSPs, die als Promise CSPs (PCSPs) bekannt ist, wachsende Aufmerksamkeit auf sich und entwickelte sich seither zu einem bedeutenden Forschungsthema. Für gegebene endliche Strukturen A, B der gleichen relationalen Signatur, so dass A homomorph auf B abbildet, kurz A -> B, beschreibt PCSP(A, B) die Frage, ob eine gegebene endliche Eingabestruktur homomorph nach A abbildet oder nicht einmal homomorph nach B abbildet. Ein vielfältig einsetzbarer Ansatz zur Untersuchung der Komplexität von PCSPs ist die Sandwiching-Methode. Wenn es eine Struktur C gibt, so dass A -> C -> B, dann reduziert sich PCSP(A, B) auf CSP(C). In diesem Fall wird C eine Sandwich-Struktur für (A, B) genannt. Barto zeigte, dass ein bestimmtes PCSP von endlichen Strukturen ein unendliches Sandwich mit in polynomieller Zeit lösbarem CSP zulässt, aber mit dieser Methode nicht auf das in Polynomialzeit lösbare CSP einer endlichen Struktur reduziert werden kann, es sei denn P = NP. Kazda, Mayr und Zhuk bewiesen, dass selbst wenn es ein endliches Sandwich mit in polynomieller Zeit lösbarem CSP gibt, die kleinste solche Struktur beliebig groß werden kann. Mottet zeigte, dass ein PCSP, welches in Logik erster Ordnung entscheidbar ist, immer auf das in Polynomialzeit lösbare CSP einer Sandwich-Struktur reduziert werden kann. In seinem Beweis konstruierte er zunächst ein ω-kategorisches Sandwich mit in polynomieller Zeit lösbarem CSP und zeigte durch ein Argument aus der Ramsey-Theorie, dass ein endlicher Faktor dieser Struktur ebenfalls ein Sandwich mit in polynomieller Zeit lösbarem CSP ist. In dieser Arbeit wird die Frage untersucht, ob es ein PCSP von endlichen Strukturen gibt, das ein ω-kategorisches Sandwich mit in polynomieller Zeit lösbarem CSP zulässt, jedoch kein endliches Sandwich mit in Polynomialzeit lösbarem CSP hat, um das Gebiet der PCSPs mit Ergebnissen über ω-kategorische CSPs zu verbinden. Während diese Frage offen bleibt, werden wir ein Beispiel für ein Paar (C, B) aus einer ω-kategorischen Struktur C mit in polynomieller Zeit lösbarem CSP und einer endlichen Struktur B mit C -> B geben, sodass das CSP jedes endlichen B′ mit C -> B′ -> B NP-vollständig ist. Außerdem werden wir eine Methode beschreiben, um weitere Paare mit dieser Eigenschaft aus bestimmten homogenen Ramsey-Strukturen zu konstruieren. Die Konstruktion einer endlichen Struktur A mit A -> C, so dass jede endliche Struktur C′ mit A -> C′ -> B NP-vollständig ist, würde eine positive Antwort auf die obige Frage geben, angenommen P ist nicht gleich NP.

Around the time when the Dichotomy Conjecture for Constraint Satisfaction Problems (CSPs) was independently proved by Bulatov and Zhuk in 2017, a generalisation of CSPs known as Promise Constraint Satisfaction Problems (PCSPs) attracted growing attention and has since developed into a significant topic of research. For given finite structures A,B of the same relational signature such that A maps homomorphically to B, denoted A -> B, PCSP(A,B) asks whether a given finite input structure maps homomorphically to A or does not even map homomorphically to B. It is promised that all input structures satisfy one of these two cases. A powerful approach to investigating the computational complexity of PCSPs is the sandwiching method. If there is some structure C such that A -> C -> B, then PCSP(A,B) reduces to CSP(C). In this case, C is called a sandwich structure for (A,B). Barto showed that a specific finite-domain PCSP admits an infinite polynomial-timetractable sandwich, but does not reduce to a tractable finite-domain CSP via this method, unless P = NP. Kazda, Mayr, and Zhuk proved that even when there exists a finite tractable sandwich, the smallest such structure may become arbitrarily large. Mottet showed that if a PCSP is first-order definable, it can always be reduced to the CSP of a finite tractable sandwich. In his proof, he first constructed a tractable ω-categorical sandwich and used a Ramsey-type argument to prove that a finite factor of this structure is also a tractable sandwich. In this thesis, we will investigate the question whether there is a finite-domain PCSP that admits a tractable ω-categorical sandwich, but no finite tractable one, aiming to connect the PCSP framework to results about ω-categorical CSPs. While this question remains open, we will provide an example of a pair (C,B) with a tractable ω-categorical structure C and a finite structure B with C -> B such that the CSP of every finite B′ with C -> B′ -> B is NP-complete. Moreover, we will describe a method to construct more pairs with this property from specific homogeneous Ramsey structures. Finding some finite structure A with A -> C such that every finite structure C′ with A -> C′ -> B is NP-complete would yield a positive answer to the above question, assuming P is not equal to NP.