Complexity of Abstract Argumentation

摘要: argumentation may be further advanced. We stress that our aim is to focus on general areas rather than particular open questions as such: the reader who has followed earlier exposition will have noted a number of specific issues already been raised in text. 6.1 Average case properties As discussed Section 5.2, lower bounds problem complexity are worstcase, so leaving possibility feasible algorithms available suitable contexts. In addition use restrictions form instances one other approach widely considered theory study average-case complexity. Underpinning this considers probability distribution, μ , decision – often, but not invariably so, uniform distribution whereby each instance equally likely, proceeding define run time an algorithm P size n L ∑x∈I(n) μ(x)ρ(P,x) where ρ(P,x) run-time x. Formal definitions classes found [36]. To date surprisingly little work carried out concerning application methods problems AFs either terms algorithmic development or considering limitations such approaches. It remains what extent techniques those applied intractable problems, e.g., [1] for NP–complete Hamiltonian cycle problem, [46] CNF satisfiability could replicated AF settings. Of some relevance approaches so-called “phase-transition” effects, which received much attention mid-late 1990s potential indicators factors separating tractable and instances, studies random CNF-SAT from [37, 40]. Analytic effects appears indicate connections between witnessing structures, satisfying assignment, being present “almost certainly” performance identify structures. interest context semantics results [41, 17] give conditions ensuring stable extension. There yet, however, no detailed implications these fast average identifying enumerating extensions. same way analyses relate 102 Paul E. Dunne Michael Wooldridge existence extensions AFs, it would examine consider solution structures consequences. 6.2 Approaches dynamic updates An important feature forms far that, practice, static systems: typically AF, 〈A,R〉, represents only “snapshot” environment, and, facts, information opinions emerge initial view change significantly order accommodate these. For example, additional arguments changing A; existing attacks cease apply new (arising changes A) come into force. clear accounting aspects raises assessing acceptability status individual arguments. with properties, treatment relating determining argument dynamically environments somewhat neglected. Thus, given 〈A,R〉 S ⊆A ∈ Es(〈A,R〉) according s, natural are: does x continue credulously accepted (w.r.t. s) 〈B,S〉 B by removing A replacing these; similarly T modifies attack relation R.