On the Complexity of Inductively Learning Guarded Clauses
Matthias Lanzinger, Georg Gottlob, Andrei Draghici
[AAAI-22] Main Track
Abstract:
We investigate the computational complexity of mining guarded clauses from clausal datasets through the framework of inductive logic programming (ILP). We show that learning guarded clauses is NP-complete and thus one step below the Sigma2-complete task of learning Horn clauses on the polynomial hierarchy. Motivated by practical applications on large datasets we identify a natural tractable fragment of the problem. Finally, we also generalise all of our results to k-guarded clauses for constant k.
Introduction Video
Sessions where this paper appears
-
Poster Session 6
Blue 5
-
Poster Session 12
Blue 5
-
Oral Session 12
Blue 5
