Some Lower Bounds for the Computational Complexity of Inductive Logic Programming

摘要

The field of Inductive Logic Programming (ILP), which is concerned with theinduction 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. The paper reviews these restrictions and proves some lower-bounds of the computational complexity of learning. In particular, it shows that a learning algorithm for i2-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. (Copyright (c) GMD 1992.)