On the Complexity of Paraconsistent Inference Relations.

Reasoning in a non-trivial way from inconsistent pieces of information is a major challenge in artificial intelligence, and its importance is reflected by the number of techniques designed so far for dealing with inconsistency (especially the few ones reported in this handbook). Many of these techniques have been investigated in depth from a logical point of view, but far less to what concerns the computational complexity aspects. The purpose of this chapter is to present in a structured way the main complexity results identified so far for paraconsistent inference based on multi-valued propositional logics. [ABSTRACT FROM AUTHOR]