[Zurück]

G. Gottlob, F. Scarcello, M. Sideri:
"Fixed-parameter complexity in AI and nonmonotonic reasoning";
Artificial Intelligence, Volume 138 (2002), 1-2; S. 55 - 86.

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 reasonig. We show that a nuber of relevant parameterized problems inthese areas are fixed-parameter tractable. Among these problems are constraint satisfaction problems with bounded trewidth 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.