Tech Reports

ULCS-02-003

On Concise Encodings of Preferred Extensions

Paul E. Dunne

Abstract

Argument Systems provide a rich abstraction within which divers concepts of reasoning, acceptability and defeasibility of arguments, etc., may be studied using a unified framework. Much work has focused on the so-called preferred extensions of such systems, which define the maximal (with respect to $subseteq$) collectively defensible subsets of arguments within a given system of arguments and attack relationship. In this article we address problems related to the following issue. Identification and enumeration of preferred extensions of an argument system is (under the usual complexity theoretic assumptions) computationally demanding: there may be exponentially many and deciding if a given subset S of X does define a preferred set is CO-NP-complete. For a domain which is questioned 'frequently' it may be acceptable to invest this computational effort once, but having done so it is desirable to encapsulate these data in a form which is compact and allows, for example, questions concerning the acceptability of specific arguments to be dealt with efficiently. In this article we consider two 'plausible' approaches to reducing the complexity of deciding if S is a preferred extension of a system H both of which assume some initial potentially 'expensive' precomputation, invested to reduce time needed in subseqent queries to the system. The first approach examines 'reasonable encoding' approaches; the second is to determine the subset of all defensible arguments providing these as additional data when attempting to decide if S is a preferred extension. It is shown that if certain properties are required of the encoding scheme, then the former approach is feasible only if NP = CO-NP. In the latter case, we show that, even if provided with information regarding which arguments are credulously accepted, the question of whether a subset of arguments defines a preferred extension remains CO-NP-complete.

Keywords: Argument Systems, Preferred Extension, Computational Complexity.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.