Some Lower Bounds for the Computational Complexity of Inductive Logic Programming
Abstract
The field of Inductive Logic Programming (ILP), which is concerned with the induction of Hornclauses from examples and background knowledge, has received increased attention over the last time. Recently, some positive results concerning the learnability of restricted logic programs have been published. In this paper we review these restrictions and prove some lower-bounds of the computational complexity of learning. In particular, we show that a learning algorithm for i 2-determinate Hornclauses (with variable i ) could be used to decide the PSPACE-complete problem of Finite State Automata Intersection, and that a learning algorithm for 12-nondeterminate Hornclauses could be used to decide the NP-complete problem of Boolean Clause Satisfiability (SAT). This also shows, that these Hornclauses are not PAC-learnable, unless RP=NP=PSPACE.
Cite
Text
Kietz. "Some Lower Bounds for the Computational Complexity of Inductive Logic Programming." European Conference on Machine Learning, 1993. doi:10.1007/3-540-56602-3_131Markdown
[Kietz. "Some Lower Bounds for the Computational Complexity of Inductive Logic Programming." European Conference on Machine Learning, 1993.](https://mlanthology.org/ecmlpkdd/1993/kietz1993ecml-some/) doi:10.1007/3-540-56602-3_131BibTeX
@inproceedings{kietz1993ecml-some,
title = {{Some Lower Bounds for the Computational Complexity of Inductive Logic Programming}},
author = {Kietz, Jörg-Uwe},
booktitle = {European Conference on Machine Learning},
year = {1993},
pages = {115-123},
doi = {10.1007/3-540-56602-3_131},
url = {https://mlanthology.org/ecmlpkdd/1993/kietz1993ecml-some/}
}