  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 $\Pi^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.
