Fixed-Parameter Complexity of Logic Programs

Title: Fixed-Parameter Complexity of Logic Programs

Research Question: Can we find better algorithms to decide the existence of models, supported models, and stable models of a certain size for logic programs, without the running time depending on the size of the program?

Methodology: The researchers used the framework of fixed-parameter complexity, which is a method used to study the complexity of parameterized problems. They considered three classes of logic programs: all finite propositional logic programs, Horn programs, and purely negative programs. They also considered three types of models: arbitrary models, supported models, and stable models.

Results: The researchers found that for a given logic program P and a fixed integer k, the problem of deciding whether P has a stable model with at most k atoms can be solved in polynomial time. However, they also found that this polynomial depends on k, which makes the algorithm impractical for large values of k.

Implications: The results of this study have implications for the field of logic programming. They show that while it is possible to find algorithms to decide the existence of certain-sized models for logic programs, these algorithms may not be practical for large values of k due to their dependence on the size of the program. This suggests that further research is needed to find better algorithms with running times that do not depend on the size of the program.

Link to Article: https://arxiv.org/abs/0107027v2 Authors: arXiv ID: 0107027v2