Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicality
This work addresses a foundational gap in computational logic for AI researchers, providing precise complexity results and scalable methods for reasoning in weighted knowledge bases.
The paper tackled the problem of determining the exact computational complexity of defeasible reasoning in many-valued weighted knowledge bases with typicality, establishing it as P^NP[log]-complete and developing new ASP encodings to handle large search spaces.
Weighted knowledge bases for description logics with typicality under a "concept-wise" multi-preferential semantics provide a logical interpretation of MultiLayer Perceptrons. In this context, Answer Set Programming (ASP) has been shown to be suitable for addressing defeasible reasoning in the finitely many-valued case, providing a $Π^p_2$ upper bound on the complexity of the problem, nonetheless leaving unknown the exact complexity and only providing a proof-of-concept implementation. This paper fulfils the lack by providing a $P^{NP[log]}$-completeness result and new ASP encodings that deal with weighted knowledge bases with large search spaces.