2022
On the Complexity of Inductively Learning Guarded Clauses
AAAI 2022technical
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 hie…