# On the Complexity of Inductively Learning Guarded Rules

arXiv: https://arxiv.org/abs/2110.03624 · HTML: https://mlsanity.com/paper/2110.03624/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 26 references that are in the map.
- First posted on arXiv 7 Oct 2021.

## Builds on (most cited first, 3 of 3)

- [Turning 30: New Ideas in Inductive Logic Programming](https://mlsanity.com/paper/2002.11002/) (2020)
- [The Vadalog System: Datalog-based Reasoning for Knowledge Graphs](https://mlsanity.com/paper/1807.08709/) (2018)
- [Synthesizing Datalog Programs Using Numerical Relaxation](https://mlsanity.com/paper/1906.00163/) (2019)

## Abstract (arXiv)

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 σP2-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.