Original title: Sliby v problémech splnitelnosti
Translated title: Promises in Satisfaction Problems
Authors: Asimi, Kristina ; Barto, Libor (advisor) ; Barnaby, Martin (referee) ; Živný, Stanislav (referee)
Document type: Doctoral theses
Year: 2023
Language: eng
Abstract: Short Abstract This thesis focuses on the complexity of the promise version of Constraint Satisfaction Problem (CSP) and its variants. The first study concerns the Promise Constraint Satisfaction Problem (PCSP), which extends the traditional CSP to include approximation variants of satisfiability and graph coloring. A specific PCSP, referred to as finding a valid Not-All-Equal solution to a 1-in- 3-SAT instance, has been shown by Barto [LICS '19] to lack finite tractability. While it can be reduced to a tractable CSP, the latter is necessarily over an infinite domain (unless P=NP). We say that such a PCSP is not finitely tractable and we initiate a systematic study of this phenomenon by giving a general necessary condition for finite tractability. Additionally, we characterize finite tractability within a class of templates. In the second study, we focus on the CSP in the context of first-order logic. The fixed-template CSP can be seen as the problem of deciding whether a given primitive positive first-order sentence is true in a fixed structure (also called model). We study a class of problems that generalizes the CSP simultaneously in two directions: we fix a set L of quantifiers and Boolean connectives, and we specify two versions of each constraint, one strong and one weak (making the promise version)....
Keywords: Constraint satisfaction problem|promise constraint satisfaction problem|finite tractability|model checking problem; problém splnitelnosti omezujících podmínek|problém splnitelnosti omezujících podmínek se slib|konečná polynomiální řešitelnost|problém ověřování sentencí v modelech

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/187622

Permalink: http://www.nusl.cz/ntk/nusl-540839


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses