On the complexity of some inductive logic programming problems

Authors
Gottlob, G Leone, N Scarcello, F
Citation
G. Gottlob et al., On the complexity of some inductive logic programming problems, NEW GEN COM, 17(1), 1999, pp. 53-75
Citations number
38
Categorie Soggetti
Computer Science & Engineering
Journal title
NEW GENERATION COMPUTING
ISSN journal
02883635 → ACNP
Volume
17
Issue
1
Year of publication
1999
Pages
53 - 75
Database
ISI
SICI code
0288-3635(1999)17:1<53:OTCOSI>2.0.ZU;2-T
Abstract
The bounded ILP-consistency problem for function-free Horn clauses is descr ibed as follows. Given a set E+ and E- of function-free ground Horn clauses and an integer I; polynomial in E+ boolean OR E-, does there exist a funct ion-free Horn clause C with no more than k literals such that C subsumes ea ch element in E+ and C does not subsume any element in E-? It is shown that this problem is Sigma(2)(P) complete. We derive some related results on th e complexity of ILP and discuss the usefulness of such complexity results.