Fixed-Parameter Complexity of Logic Programs

Title: Fixed-Parameter Complexity of Logic Programs

Research Question: Can we find algorithms with running times that do not depend on the size of the parameter k, for deciding the existence of models, supported models, and stable models of logic programs?

Methodology: The researchers used the framework of fixed-parameter complexity, which is a method used to study the efficiency of algorithms when a problem's input size depends on an additional parameter. They considered three classes of logic programs: all finite propositional logic programs, Horn programs, and purely negative programs. They also studied three types of models: arbitrary models, supported models, and stable models.

Results: The researchers found that most of the problems they studied have high fixed-parameter complexity, meaning that it is unlikely that fixing bounds on models will lead to fast algorithms for deciding their existence. They also found that restricting attention to Horn programs and purely negative programs does not necessarily make the problems easier.

Implications: These results suggest that there may not be efficient algorithms for deciding the existence of models, supported models, and stable models of logic programs, especially for larger values of the parameter k. This could have implications for the practical application of these algorithms in areas such as artificial intelligence and computer science.

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