On the Complexity of Inductively Learning Guarded Clauses
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.
Cite
Text
Draghici et al. "On the Complexity of Inductively Learning Guarded Clauses." AAAI Conference on Artificial Intelligence, 2022. doi:10.1609/AAAI.V36I5.20500Markdown
[Draghici et al. "On the Complexity of Inductively Learning Guarded Clauses." AAAI Conference on Artificial Intelligence, 2022.](https://mlanthology.org/aaai/2022/draghici2022aaai-complexity/) doi:10.1609/AAAI.V36I5.20500BibTeX
@inproceedings{draghici2022aaai-complexity,
title = {{On the Complexity of Inductively Learning Guarded Clauses}},
author = {Draghici, Andrei and Gottlob, Georg and Lanzinger, Matthias},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2022},
pages = {5600-5607},
doi = {10.1609/AAAI.V36I5.20500},
url = {https://mlanthology.org/aaai/2022/draghici2022aaai-complexity/}
}