On the Complexity of Inductively Learning Guarded Clauses

No. 5: AAAI-22 Technical Tracks 5

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 36

AAAI Technical Track on Knowledge Representation and Reasoning

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.

10.1609/aaai.v36i5.20500