Název: Sliby v problémech splnitelnosti
Překlad názvu: Promises in Satisfaction Problems
Autoři: Asimi, Kristina ; Barto, Libor (vedoucí práce) ; Barnaby, Martin (oponent) ; Živný, Stanislav (oponent)
Typ dokumentu: Disertační práce
Rok: 2023
Jazyk: eng
Abstrakt: 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)....
Klíčová slova: 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; Constraint satisfaction problem|promise constraint satisfaction problem|finite tractability|model checking problem

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/187622

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-540839


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Disertační práce