The complexity of revising logic programs

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 retu rn different answers if its rules are re-ordered. There are also many reaso ning 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 syste ms. A theory revision algorithm, seeking a revised rule-base whose expected accuracy, over the distribution of queries, is optimal, should therefore c onsider modifying the order of the rules. This paper first shows that a pol ynomial 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 determinin g which ordering is optimal, once given this distributional information, is intractable even in trivial situations; e.g., even if each query is an ato mic literal, we are seeking only a "perfect" theory, and the rule base is p ropositional. 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 gamma > 0. We next prove similar hardness and non-approximatability, results for the rel ated tasks of determining, in these impure contexts, (1) the optimal orderi ng of the antecedents; (2) the optimal set of new rules to add and (3) the optimal set of existing rules to delete. (C) 1999 Elsevier Science Inc. All rights reserved.