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

Complexity Classifications for Logic-Based ArgumentationPrimeFaces.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}); 2014 (English)In: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 15, no 3, 19Article in journal (Refereed) Published
##### Abstract [en]

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

Association for Computing Machinery (ACM) , 2014. Vol. 15, no 3, 19
##### Keyword [en]

Theory; Computational complexity; generalized satisfiability; logic-based argumentation; Schaefer
##### National Category

Computer and Information Science
##### Identifiers

URN: urn:nbn:se:hj:diva-31616DOI: 10.1145/2629421ISI: 000343693300002Scopus ID: 2-s2.0-84907578385OAI: oai:DiVA.org:hj-31616DiVA: diva2:957120
#####

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt467",{id:"formSmash:j_idt467",widgetVar:"widget_formSmash_j_idt467",multiple:true});
##### Note

We consider logic-based argumentation in which an argument is a pair (Phi, alpha), where the support Phi is a minimal consistent set of formulae taken from a given knowledge base (usually denoted by Delta) that entails the claim alpha (a formula). We study the complexity of three central problems in argumentation: the existence of a support Phi subset of Delta, the verification of a support, and the relevance problem (given psi, is there a support Phi such that psi is an element of Phi?). When arguments are given in the frill language of propositional logic, these problems are computationally costly tasks: the verification problem is DP-complete; the others are Sigma(P)(2)-complete. We study these problems in Schaefers famous framework where the considered propositional formulae are in generalized conjunctive normal form. This means that formulae are conjunctions of constraints built upon a fixed finite set of Boolean relations Gamma (the constraint language). We show that according to the properties of this language Gamma, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete, or Sigma(P)(2)-complete. We present a dichotomous classification, P or DP-complete, for the verification problem and a trichotomous classification for the relevance problem into either polynomial, NP-complete, or Sigma(P)(2)-complete. These last two classifications are obtained by means of algebraic tools.

Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden; Austrian Science Foundation (FWF) [S11409-N23]

Available from: 2014-11-28 Created: 2016-09-01 Last updated: 2016-09-01Bibliographically approvedCiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1195",{id:"formSmash:lower:j_idt1195",widgetVar:"widget_formSmash_lower_j_idt1195",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1196_j_idt1198",{id:"formSmash:lower:j_idt1196:j_idt1198",widgetVar:"widget_formSmash_lower_j_idt1196_j_idt1198",target:"formSmash:lower:j_idt1196:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});