CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt144",{id:"formSmash:upper:j_idt144",widgetVar:"widget_formSmash_upper_j_idt144",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt145_j_idt147",{id:"formSmash:upper:j_idt145:j_idt147",widgetVar:"widget_formSmash_upper_j_idt145_j_idt147",target:"formSmash:upper:j_idt145:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Strong Partial Clones and the Complexity of Constraint Satisfaction Problems: Limitations and ApplicationsPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
2016 (English)Doctoral thesis, monograph (Other academic)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Linköping: Linköping University Electronic Press, 2016. , p. 160
##### Series

Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1733
##### National Category

Computer Sciences
##### Identifiers

URN: urn:nbn:se:liu:diva-122827DOI: 10.3384/diss.diva-122827ISBN: 978-91-7685-856-1 (print)OAI: oai:DiVA.org:liu-122827DiVA, id: diva2:874097
##### Public defence

2016-02-03, Alan Turing, hus E, Campus Valla, Linköpiong, 13:15 (English)
##### Opponent

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt434",{id:"formSmash:j_idt434",widgetVar:"widget_formSmash_j_idt434",multiple:true});
##### Supervisors

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt440",{id:"formSmash:j_idt440",widgetVar:"widget_formSmash_j_idt440",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt446",{id:"formSmash:j_idt446",widgetVar:"widget_formSmash_j_idt446",multiple:true});
##### Funder

CUGS (National Graduate School in Computer Science)Available from: 2015-12-15 Created: 2015-11-25 Last updated: 2018-01-10Bibliographically approved

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*. In particular, we consider algebras of *partial functions*, called *strong partial clones*. This algebraic approach allows us to obtain a more nuanced view of the complexity CSP(S) than possible with algebras of total functions, *clones*.

The results of this thesis is split into two main parts. In the first part we investigate properties of strong partial clones, beginning with a classification of* weak* bases for all Boolean relational clones. Weak bases are constraint languages where the corresponding strong partial clones in a certain sense are extraordinarily large, and they provide a rich amount of information regarding the complexity of the corresponding CSP problems. We then proceed by classifying the Boolean relational clones according to whether it is possible to represent every relation by a conjunctive, logical formula over the weak base without needing more than a polynomial number of existentially quantified variables. A relational clone satisfying this condition is called *polynomially closed* and we show that this property has a close relationship with the concept of *few subpowers.* Using this classification we prove that a strong partial clone is of *infinite orde*r if (1) the total functions in the strong partial clone are essentially unary and (2) the corresponding constraint language is finite. Despite this, we prove that these strong partial clones can be succinctly represented with finite sets of partial functions, bounded bases, by considering stronger notions of closure than functional composition.

In the second part of this thesis we apply the theory developed in the first part. We begin by studying the complexity of CSP(S) where *S* is a Boolean constraint language, the generalised satisfiability problem (SAT(S)). Using weak bases we prove that there exists a relation R such that SAT({R}) is the easiest NP*-complete* SAT(S) problem. We rule out the possibility that SAT({R}) is solvable in subexponential time unless a well-known complexity theoretical conjecture, the *exponential-time hypothesis, (*ETH) is false. We then proceed to study the computational complexity of two optimisation variants of the SAT(S) problem: the *maximum ones problem* over a Boolean constraint language *S* (MAX-ONES(*S*)) and the v*alued constraint satisfaction* *problem* over a set of Boolean cost functions Δ (VCSP(Δ)). For MAX-ONES(*S*) we use partial clone theory and prove that MAX-ONES({R}) is the easiest NP-complete MAX-ONES(S) problem. These algebraic techniques do not work for VCSP(Δ), however, where we instead use *multimorphisms* to prove that MAX-CUT is the easiest NP-complete Boolean VCSP(Δ) problem. Similar to the case of SAT(*S*) we then rule out the possibility of subexponential algorithms for these problems, unless the ETH is false.

doi
isbn
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1156",{id:"formSmash:j_idt1156",widgetVar:"widget_formSmash_j_idt1156",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1209",{id:"formSmash:lower:j_idt1209",widgetVar:"widget_formSmash_lower_j_idt1209",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1210_j_idt1212",{id:"formSmash:lower:j_idt1210:j_idt1212",widgetVar:"widget_formSmash_lower_j_idt1210_j_idt1212",target:"formSmash:lower:j_idt1210:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});