Complexity Classifications for Propositional Abduction in Post's Framework

Nadia Creignou, Johannes Schmidt, Michael Thomas

In this paper we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining the world's behavior it aim…