Fixed-parameter complexity in Al and nonmonotonic reasoning

Georg Gottlob

doi:10.1016/S0004-3702(02)00182-0

Fixed-parameter complexity in Al and nonmonotonic reasoning

2002-06-01

70

PRE

AI

DOI：10.1016/S0004-3702(02)00182-0

Original

Original request for help

Save

Abstract

En 中文

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. (C) 2002 Elsevier Science B.V. All rights reserved.

Keywords:

parameterized complexity

fixed-parameter tractability

nonmonotonic reasoning

constraint satisfaction

conjunctive queries

prime implicants

logic programming

stable models

circumscription

Fixed-parameter complexity in Al and nonmonotonic reasoning

Abstract

AI Summary

Journal

Organization