Fixed-Parameter Complexity of Logic Programs: Difference between revisions
Created page with "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 conside..." |
No edit summary |
||
| Line 1: | Line 1: | ||
Title: Fixed-Parameter Complexity of Logic Programs | Title: Fixed-Parameter Complexity of Logic Programs | ||
Research Question: Can we find algorithms | 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 | 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 | 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: | 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/ | Link to Article: https://arxiv.org/abs/0107027v2 | ||
Authors: | Authors: | ||
arXiv ID: | arXiv ID: 0107027v2 | ||
[[Category:Computer Science]] | [[Category:Computer Science]] | ||
[[Category:Models]] | [[Category:Models]] | ||
[[Category:Logic]] | |||
[[Category:Programs]] | [[Category:Programs]] | ||
[[Category: | [[Category:K]] | ||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
Latest revision as of 02:40, 24 December 2023
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