On the Complexity of Linking Deductive and Abstract Argument Systems

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Knowledge Representation and Logic

We investigate the computational complexity of a number of questions relating to deductive argument systems, in particular the complexity of linking deductive and more abstract argument systems. We start by presenting a simple model of deductive arguments based on propositional logic, and define logical equivalence and defeat over individual arguments. We then extend logical equivalence to sets of arguments, and show that the problem of checking equivalence of argument sets is co-NP-complete. We also show that the problem of checking that an argument set contains no two logically equivalent arguments is NP-complete, while the problem of checking that a set of arguments is maximal (i.e., that no argument could be added without such an argument being logically equivalent to one that is already present) is co-NP-complete. We then show that checking whether a digraph over an argument set is sound with respect to the defeat relation is co-NP-complete, while the problem of showing that such a digraph is complete is NP-complete, and the problem of showing both soundness and completeness is D^p-complete.