## Abstract

In this paper, we focus on the problem of existence and computing of small and large stable models. We show that for every fixed integer k, there is a linear-time algorithm to decide the problem LSM (large stable models problem): does a logic program P have a stable model of size at least |P|-k? In contrast, we show that the problem SSM (small stable models problem) to decide whether a logic program P has a stable model of size at most k is much harder. We present two algorithms for this problem but their running time is given by polynomials of order depending on k. We show that the problem SSM is fixed-parameter intractable by demonstrating that it is W[2]-hard. This result implies that it is unlikely an algorithm exists to compute stable models of size at most k that would run in time O(m^{c}), where m is the size of the program and c is a constant independent of k. We also provide an upper bound on the fixed-parameter complexity of the problem SSM by showing that it belongs to the class W[3].

Original language | English |
---|---|

Pages (from-to) | 1-23 |

Number of pages | 23 |

Journal | Theory and Practice of Logic Programming |

Volume | 2 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2002 |

## Keywords

- Fixed-parameter complexity
- Stable models

## ASJC Scopus subject areas

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics
- Artificial Intelligence