View Publication

The Complexity of Revising Logic Programs

Russ Greiner, Dept of Computing Science; PI of AICML

Other Attachments:

A rule-based program will return a set of answers to each query. An impure program, which includes the Prolog cut "!" and not(.) operators, can return different answers if its rules are re-ordered. There are also many reasoning systems that return only the first answer found for each query; these first answers, too, depend on the rule order, even in pure rule-based systems. A theory revision algorithm, seeking a revised rule-base whose expected accuracy, over the distribution of queries, is optimal, should therefore consider modifying the order of the rules. This paper first shows that a polynomial number of training "labeled queries" (each a query paired with its correct answer) provides the distribution information necessary to identify the optimal ordering. It then proves, however, that the task of determining which ordering is optimal, once given this distributional information, is intractable even in trivial situations; eg, even if each query is an atomic literal, we are seeking only a "perfect" theory, and the rule base is propositional. We also prove that this task is not even approximable: Unless P=NP, no polynomial time algorithm can produce an ordering of an n-rule theory whose accuracy is within n^{gamma} of optimal, for some γ > 0. We next prove similar hardness, and non-approximatability, results for the related tasks of determining, in these impure contexts, (1) the optimal ordering of the antecedents; (2) the optimal set of new rules to add; and (3) the optimal set of existing rules to delete.

Citation

R. Greiner. "The Complexity of Revising Logic Programs". Journal of Logic Programming, 40(2--3), pp 273--298, August 1999.

Keywords:	logic programs, theory revision, machine learning, impure
Category:	In Journal

BibTeX

@article{Greiner:J.LogicProgramming99,
  author = {Russ Greiner},
  title = {The Complexity of Revising Logic Programs},
  Volume = "40",
  Number = "2--3",
  Pages = {273--298},
  journal = {Journal of Logic Programming},
  year = 1999,
}

Last Updated: April 25, 2007
Submitted by Nelson Loyola

Not Logged In

PapersDB

The Complexity of Revising Logic Programs

Citation

BibTeX