On the Complexity of Inductively Learning Guarded Clauses
Authors: Andrei Draghici, Georg Gottlob, Matthias Lanzinger5600-5607
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 ΣP 2 -complete task of learning Horn clauses on the polynomial hierarchy. Motivated by practical applications on large datasets we identify a natural tractable fragment of the problem. Finally, we also generalise all of our results to k-guarded clauses for constant k. |
| Researcher Affiliation | Academia | Andrei Draghici, Georg Gottlob, Matthias Lanzinger University of Oxford andrei.draghici@stcatz.ox.ac.uk, georg.gottlob@cs.ox.ac.uk, matthias.lanzinger@cs.ox.ac.uk |
| Pseudocode | Yes | Algorithm 1: A polynomial time algorithm for ILP consistency for setting G . |
| Open Source Code | No | The paper does not provide any statement about releasing source code or a link to a code repository for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical complexity analysis and algorithm design for learning from abstract "clausal datasets" or "ground clauses" as "examples". It does not involve empirical training on specific, publicly available datasets for which access information would be provided. |
| Dataset Splits | No | The paper does not conduct empirical experiments with dataset splits (training, validation, test). It focuses on theoretical analysis. |
| Hardware Specification | No | The paper does not conduct empirical experiments that would require specific hardware for execution, and thus does not specify any hardware details. |
| Software Dependencies | No | The paper is theoretical, presenting an algorithm and complexity analysis. It does not mention any specific software names with version numbers that would be required to reproduce any empirical experiments. |
| Experiment Setup | No | The paper describes theoretical results and an algorithm. It does not provide details on an experimental setup such as hyperparameters or training configurations, as it does not conduct empirical experiments. |