liu.seSearch for publications in DiVA

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt145",{id:"formSmash:upper:j_idt145",widgetVar:"widget_formSmash_upper_j_idt145",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt146_j_idt148",{id:"formSmash:upper:j_idt146:j_idt148",widgetVar:"widget_formSmash_upper_j_idt146_j_idt148",target:"formSmash:upper:j_idt146:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Complexity Dichotomies for CSP-related ProblemsPrimeFaces.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();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2007 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

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

Institutionen för datavetenskap , 2007. , 36 p.
##### Series

Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1091
##### Keyword [en]

Complexity, Constraint Satisfaction Problem, System of Equations, Nonmonotonic Logic, Circumscription, Abduction, Isomorphism
##### National Category

Computer Science
##### Identifiers

URN: urn:nbn:se:liu:diva-8822ISBN: 978–91–85715–20–6OAI: oai:DiVA.org:liu-8822DiVA: diva2:23528
##### Public defence

2007-06-01, Visionen, Hus B, Campus Valla, Linköping University, Linköping, 13:15 (English)
##### Opponent

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt387",{id:"formSmash:j_idt387",widgetVar:"widget_formSmash_j_idt387",multiple:true});
Available from: 2007-05-03 Created: 2007-05-03 Last updated: 2009-09-08Bibliographically approved
##### List of papers

Ladner’s theorem states that if **P** ≠ **NP**, then there are problems in **NP** that are neither in **P** nor **NP**-complete. Csp(Γ) is a class of problems containing many well-studied combinatorial problems in **NP**. Csp(Γ) problems are of the form: given a set of variables constrained by a set of constraints from the set of allowed constraints Γ, is there an assignment to the variables satisfying all constraints? A famous, and in the light of Ladner’s theorem, surprising conjecture states that there is a complexity dichotomy for Csp(Γ); that is, for any fixed finite Γ, the Csp(Γ) problem is either in **P** or **NP**-complete.

In this thesis we focus on problems expressible in the Csp(Γ) framework with different computational goals, such as: counting the number of solutions, deciding whether two sets of constraints have the same set of solutions, deciding whether all minimal solutions of a set of constraints satisfies an additional constraint etc. By doing so, we capture a host of problems ranging from fundamental problems in nonmonotonic logics, such as abduction and circumscription, to problems regarding the equivalence of systems of linear equations. For several of these classes of problem, we are able to give complete complexity classifications and rule out the possibility of problems of intermediate complexity. For example, we prove that the inference problem in propositional variable circumscription, parameterized by the set of allowed constraints Γ, is either in **P**, **coNP**-complete, or **ΠP/2**-complete. As a by-product of these classifications, new tractable cases and hardness results for well-studied problems are discovered.

The techniques we use to obtain these complexity classifications are to a large extent based on connections between algebraic clone theory and the complexity of Csp(Γ). We are able to extend these powerful algebraic techniques to several of the problems studied in this thesis. Hence, this thesis also contributes to the understanding of when these algebraic techniques are applicable and not.

1. The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups$(function(){PrimeFaces.cw("OverlayPanel","overlay23523",{id:"formSmash:j_idt423:0:j_idt427",widgetVar:"overlay23523",target:"formSmash:j_idt423:0:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

2. The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups$(function(){PrimeFaces.cw("OverlayPanel","overlay23524",{id:"formSmash:j_idt423:1:j_idt427",widgetVar:"overlay23524",target:"formSmash:j_idt423:1:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

3. An Algebraic Approach to the Complexity of Propositional Circumscription$(function(){PrimeFaces.cw("OverlayPanel","overlay23525",{id:"formSmash:j_idt423:2:j_idt427",widgetVar:"overlay23525",target:"formSmash:j_idt423:2:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

4. A Trichotomy in the Complexity of Propositional Circumscription$(function(){PrimeFaces.cw("OverlayPanel","overlay23526",{id:"formSmash:j_idt423:3:j_idt427",widgetVar:"overlay23526",target:"formSmash:j_idt423:3:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

5. Propositional Abduction is Almost Always Hard$(function(){PrimeFaces.cw("OverlayPanel","overlay23527",{id:"formSmash:j_idt423:4:j_idt427",widgetVar:"overlay23527",target:"formSmash:j_idt423:4:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1080",{id:"formSmash:lower:j_idt1080",widgetVar:"widget_formSmash_lower_j_idt1080",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1081_j_idt1083",{id:"formSmash:lower:j_idt1081:j_idt1083",widgetVar:"widget_formSmash_lower_j_idt1081_j_idt1083",target:"formSmash:lower:j_idt1081:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});