Praca doktorska
Extended constraint satisfaction problems
| dc.abstract.en | To solve an instance of the constraint satisfaction problem (CSP) one has to find an assignment of values to variables that satisfies given constraints. This thesis concerns two different extensions of the constraint satisfaction problem.The first extension allows for an infinite number of constraints in an instance. It is phrased in the language of sets with atoms, which provides finite means of representation -- an instance is founded upon a fixed infinite relational structure, and defined by finitely many first order formulas. We prove decidability for this so-called locally finite CSP, and establish tight complexity bounds in the special case when the set of possible values is finite.We further use the constraint satisfaction framework to analyse the computational model of Turing machines with atoms (TMAs), whose alphabet, state space, and transition relation are orbit-finite sets with atoms (usually infinite but finitely presentable). We give an effective characterisation of those alphabets for which TMAs determinise, with applications to descriptive complexity.The second extension of the CSP that we consider is known as the valued constraint satisfaction problem (VCSP). It provides a common framework for many discrete optimisation problems. We use algebraic tools to establish a necessary condition for tractability of VCSPs parametrised by sets of allowed types of constraints. We conjecture that our condition is also sufficient, and verify whether the conjecture agrees with all previously known results. |
| dc.abstract.pl | Aby rozwiązać daną instancję problemu spełnialności więzów, należy znaleźć takie przypisanie wartości do zmiennych, żeby spełnione były wszystkie więzy. Ta rozprawa dotyczy dwóch rozszerzeń problemu spełnialności więzów.Pierwsze rozszerzenie dopuszcza nieskończenie wiele więzów w instancji. Jest ono sformalizowane w języku teorii zbiorów z atomami, który pozwala na skończoną reprezentację -- dla ustalonej nieskończonej struktury relacyjnej każda instancja zadana jest przez skończenie wiele formuł logiki pierwszego rzędu. Dowodzimy, że ten problem, który nazywamy lokalnie skończonym problemem spełnialności więzów, jest rozstrzygalny. Podajemy także ścisłe oszacowanie jego złożoności obliczeniowej w szczególnym przypadku, gdy liczba możliwych war- tości jest skończona.Następnie stosujemy narzędzia teorii spełnialności więzów do analizy mo- delu obliczeniowego maszyn Turinga z atomami, których alfabet, zbiór stanów, oraz relacja przejścia są orbitowo-skończonymi zbiorami z atomami (są one zazwyczaj nieskończone, ale możliwa jest ich skończona reprezentacja). Uzyskujemy efektywną charakteryzację tych alfabetów, dla których maszyny Turinga z atomami się determinizują, a ponadto pokazujemy zastosowanie tego wyniku do teorii złożoności opisowej. Drugie rozpatrywane przez nas rozszerzenie problemu spełnialności więzów jest znane jako problem spełnialności więzów z wartościami. Pozwala ono na formalizację wielu dyskretnych problemów optymalizacyjnych. Używając narzędzi algebraicznych ustanawiamy warunek konieczny, aby problem spełnialności wię- zów z wartościami, sparametryzowany przez ustalony zbiór dopuszczalnych typów więzów, był rozwiązywalny w czasie wielomianowym. Formułujemy ponadto hipotezę, która głosi, że podany przez nas warunek jest jednoczeście dostateczny i sprawdzamy jej zgodność ze wszystkimi znanymi wcześniej wynikami. |
| dc.affiliation.department | Wydział Matematyki, Informatyki i Mechaniki |
| dc.contributor.author | Ochremiak, Joanna |
| dc.date.accessioned | 2016-02-12T00:05:40Z |
| dc.date.available | 2016-02-12T00:05:40Z |
| dc.date.defence | 2016-02-24 |
| dc.date.issued | 2015-09-24 |
| dc.description.additional | Link archiwalny https://depotuw.ceon.pl/handle/item/1411 |
| dc.description.osid | 67468 |
| dc.description.promoter | Klin, Bartosz |
| dc.description.promoter | Toruńczyk, Szymon |
| dc.identifier.apd | 19811 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/1411 |
| dc.language.iso | en |
| dc.rights | ClosedAccess |
| dc.subject.en | constraint satisfaction problems |
| dc.subject.en | sets with atoms |
| dc.subject.en | valued constraint satisfaction |
| dc.subject.pl | problemy spełnialności więzów |
| dc.subject.pl | zbiory z atomami |
| dc.subject.pl | spełnialność więzów z wartościami |
| dc.title | Extended constraint satisfaction problems |
| dc.title.alternative | Rozszerzone problemy spełnialności więzów |
| dc.type | DoctoralThesis |
| dspace.entity.type | Publication |