|
|
Promises in Satisfaction Problems
Asimi, Kristina ; Barto, Libor (advisor) ; Barnaby, Martin (referee) ; Živný, Stanislav (referee)
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)....
|
|
|
Relation between accepting languages and complexity of guestions on oracle
Živný, Stanislav
Denote X the class of sets relative to which P = NP relativized and Z the class of sets relative to which P 6= NP. Besides presenting known properties about X and Z, we also show that complete problems for exponential complexity classes and stronger ones belong to X. We show that some complete problems, if they ever exist, for deterministic classes between polynomial and exponential time do not belong to X. We show that hard problems for exponential classes do not generally belong to X. We characterize sets in X as the sets in the intersection of the first level of the extended low and the zeroth level of the extended high hierarchy. Further, we prove that neither X nor Z is closed under unions, intersections and symmetric differences. We also prove that Z is not closed under disjoint unions which implies that disjoint union can lower complexity measured in terms of extended lowness.
|
|
|
Relation between accepting languages and complexity of guestions on oracle
Živný, Stanislav
Denote X the class of sets relative to which P = NP relativized and Z the class of sets relative to which P 6= NP. Besides presenting known properties about X and Z, we also show that complete problems for exponential complexity classes and stronger ones belong to X. We show that some complete problems, if they ever exist, for deterministic classes between polynomial and exponential time do not belong to X. We show that hard problems for exponential classes do not generally belong to X. We characterize sets in X as the sets in the intersection of the first level of the extended low and the zeroth level of the extended high hierarchy. Further, we prove that neither X nor Z is closed under unions, intersections and symmetric differences. We also prove that Z is not closed under disjoint unions which implies that disjoint union can lower complexity measured in terms of extended lowness.
|
guest ::
