Paper Info
Title
Fixed-parameter complexity in AI and nonmonotonic reasoning
Abstract
Many relevant intractable problems become tractable if some problem parameter is fixed. However, various problems exhibit very different computational properties, depending on how the runtime required for solving them is related to the fixed parameter chosen. The theory of parameterized complexity deals with such issues, and provides general techniques for identifying fixed-parameter tractable and fixed-parameter intractable problems. We study the parameterized complexity of various problems in AI and nonmonotonic reasoning. We show that a number of relevant parameterized problems in these areas are fixed-parameter tractable. Among these problems are constraint satisfaction problems with bounded treewidth and fixed domain, restricted forms of conjunctive database queries, restricted satisfiability problems, propositional logic programming under the stable model semantics where the parameter is the dimension of a feedback vertex set of the program's dependency graph, and circumscriptive inference from a positive k-CNF restricted to models of bounded size. We also show that circumscriptive inference from a general propositional theory, when the attention is restricted to models of bounded size, is fixed-parameter intractable and is actually complete for a novel fixed-parameter complexity class.
Year
DOI
Venue
1999
10.1016/S0004-3702(02)00182-0
Artif. Intell.
Keywords
DocType
Volume
complexity class,nonmonotonic reasoning,circumscription,stable model semantics,propositional logic,constraint satisfaction,feedback vertex set,prime implicants,logic programming,satisfiability,conjunctive queries,constraint satisfaction problem,parameterized complexity
Conference
138
Issue
ISSN
ISBN
1-2
0004-3702
3-540-66749-0
Citations 
PageRank 
References 
40
1.69
29
Authors
3
Name
Order
Citations
PageRank
Georg Gottlob195941103.48
Francesco Scarcello22381132.62
Martha Sideri340946.17