On the complexity of some Inductive Logic Programming problems

The bounded ILP-consistency problem for function-free Horn clauses is described as follows. Given a set E+ and E− of function-free ground Horn clauses and an integer k polynomial in E+∪E−, does there exist a function-free Horn clause C with no more than k literais such that C subsumes each element in E+ and C does not subsume any element in E−. It is shown that this problem is Σ₂P complete. We derive some related results on the complexity of ILP and discuss the usefulness of such complexity results.