Advanced search

Found 2 swedish dissertations matching the above criteria.

2. 1. Strong Partial Clones and the Complexity of Constraint Satisfaction Problems : Limitations and Applications

   Author : Victor Lagerkvist; Peter Jonsson; Christer Bäckström; Nadia Creignou; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES;

   Abstract : In this thesis we study the worst-case time complexity of the constraint satisfaction problem parameterized by a constraint language (CSP(S)), which is the problem of determining whether a conjunctive formula over S has a model. To study the complexity of CSP(S) we borrow methods from universal algebra. READ MORE

4. 2. Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems

   Author : Biman Roy; Peter Jonsson; Victor Lagerkvist; Arnaud Durand; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES;

   Abstract : In this thesis we study the worst-case complexity ofconstraint satisfaction problems and some of its variants. We use methods from universal algebra: in particular, algebras of total functions and partial functions that are respectively known as clones and strong partial clones. READ MORE