|
|
Promises in Satisfaction Problems
Asimi, Kristina ; Barto, Libor (vedoucí práce) ; Barnaby, Martin (oponent) ; Živný, Stanislav (oponent)
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
Označme X třídu množin, vzhledem k nimž P = NP relativizovaně a Z třídu množin, vzhledem k nimž P 6= NP. Vedle známých vlastností těchto tříd ukážeme, že úplné úlohy ponenciálních složitostních tříd a silnějších patří do X. Ukážeme, že některé úplné úlohy, pokud vůbec existují, deterministických složitostních tříd definovaných časovou složitostí větší než polynomiální a menší než exponenciální, nepatří do X. Ukážeme, že těžké problémy exponenciálních tříd nemusí nutně patřit do X. Charakterizujeme množiny z X jako množiny ležící v průniku prvního stupně rozšíření dolní a nultého stupně rozšířené horní hierarchie. Dokážeme, že X ani Z nejsou uzavřené vůči operacím průnik, sjednocení a symetrická diference. Dále dokížeme, že Z není uzavřena vůči disjunktnímu sjednocení, z čehož vyplývá, že disjunktní sjednocení může snížit složitost měřenou vztahem k rozšířené dolní hierarchii.
|
|
|
Relation between accepting languages and complexity of guestions on oracle
Živný, Stanislav
Označme X třídu množin, vzhledem k nimž P = NP relativizovaně a Z třídu množin, vzhledem k nimž P 6= NP. Vedle známých vlastností těchto tříd ukážeme, že úplné úlohy ponenciálních složitostních tříd a silnějších patří do X. Ukážeme, že některé úplné úlohy, pokud vůbec existují, deterministických složitostních tříd definovaných časovou složitostí větší než polynomiální a menší než exponenciální, nepatří do X. Ukážeme, že těžké problémy exponenciálních tříd nemusí nutně patřit do X. Charakterizujeme množiny z X jako množiny ležící v průniku prvního stupně rozšíření dolní a nultého stupně rozšířené horní hierarchie. Dokážeme, že X ani Z nejsou uzavřené vůči operacím průnik, sjednocení a symetrická diference. Dále dokížeme, že Z není uzavřena vůči disjunktnímu sjednocení, z čehož vyplývá, že disjunktní sjednocení může snížit složitost měřenou vztahem k rozšířené dolní hierarchii.
|
host ::
RSS.