Sökning: "Victor Lagerkvist"
Hittade 2 avhandlingar innehållade orden Victor Lagerkvist.
1. Strong Partial Clones and the Complexity of Constraint Satisfaction Problems : Limitations and Applications
Sammanfattning : 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. LÄS MER
2. Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems
Sammanfattning : 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. LÄS MER