Fixed-parameter complexity of semantics for logic programs

Details Fixed-parameter complexity of semantics for logic programs Fixed-parameter complexity of semantics for logic programs

2001-07-19

arxiv.org/abs/cs/0107027v2

ACM Transactions on Computational Logic, 4 (2003), pp. 91-119.

Computer Science

Logic in Computer Science

Submission to ACM TOCL; full version of the paper published in the Proceedings of ICLP 2001 (Springer Verlag)

Scientific paper

A decision problem is called parameterized if its input is a pair of strings. One of these strings is referred to as a parameter. The problem: given a propositional logic program P and a non-negative integer k, decide whether P has a stable model of size no more than k, is an example of a parameterized decision problem with k serving as a parameter. Parameterized problems that are NP-complete often become solvable in polynomial time if the parameter is fixed. The problem to decide whether a program P has a stable model of size no more than k, where k is fixed and not a part of input, can be solved in time O(mn^k), where m is the size of P and n is the number of atoms in P. Thus, this problem is in the class P. However, algorithms with the running time given by a polynomial of order k are not satisfactory even for relatively small values of k. The key question then is whether significantly better algorithms (with the degree of the polynomial not dependent on k) exist. To tackle it, we use the framework of fixed-parameter complexity. We establish the fixed-parameter complexity for several parameterized decision problems involving models, supported models and stable models of logic programs. We also establish the fixed-parameter complexity for variants of these problems resulting from restricting attention to Horn programs and to purely negative programs. Most of the problems considered in the paper have high fixed-parameter complexity. Thus, it is unlikely that fixing bounds on models (supported models, stable models) will lead to fast algorithms to decide the existence of such models.

Affiliated with

Also associated with

No associations

Rating

Fixed-parameter complexity of semantics for logic programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fixed-parameter complexity of semantics for logic programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fixed-parameter complexity of semantics for logic programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-657544