Abstract
We study the fixed-parameter 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 satisfiability problems, prepositional 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
K. Apt, H. Blair, and A. Walker. Towards a Theory of Declarative Knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 89–148. Morgan Kaufman, Washington DC, 1988.
W. Bibel. Constraint Satisfaction from a DeductiveViewpoint. Artificial Intelligence, 35,401–413, 1988.
H. L. Bodlaender.A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305–1317, 1996.
A.K. Chandra and P.M. Merlin. Optimal Implementation of Conjunctive Queries in relational Databases. In ACM Symp. on Theory of Computing (STOC’77), pp.77–90, 1977.
R.G. Downey and M.R. Fellows. Fixed ParameterTractability and Completeness. Congressus Numerantium, 87:161–187, 1992.
R.G. Downey and M.R. Fellows. Fixed Parameter Intractability (Extended Abstract). In Proc. of Structure in Complexity Theory, IEEE, pp.36–50, 1992.
R.G. Downey and M.R. Fellows. Fixed Parameter Tractability and Completeness I: Basic Results. SIAM J. Comput., 24:873–921, 1995.
R.G. Downey and M.R. Fellows. On the Parametric Complexity of Relational Database Queries and a Sharper Characterization of W[1]. In Combinatorics Complexity and Logics, Proceedings of DMTCS’96, pp.164–213, Springer, 1996.
R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer, NewYork, 1999.
T. Eiter and G. Gottlob. Propositional Circumscription and Extended ClosedWorld Reasoning are IIstackP stack2-complete. Theoretical Computer Science, 114(2):231–245, 1993. Addendum 118:315.
T. Eiter, G. Gottlob, and H. Mannila. Disjunctive Datalog. ACM Trans. on Database Syst., 22(3):364–418, September 1997.
S. Fortune, J.E. Hopcroft, and J. Wyllie. The Directed Subgraph Homeomorphism Problem. Theoretical Computer Science, 10(2): 111–121, 1980.
M.R. Garey and D.S. Johnson. Computers and Intractability. A Guide to the Theory of NPcompleteness. Freeman and Comp., NY, USA, 1979.
M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Logic Programming: Proc. Fifth Intl Conference and Symposium, pp. 1070–1080, Cambridge, Mass., 1988. MIT Press.
G. Gottlob, N. Leone, and F. Scarcello. The Complexity of Acyclic Conjunctive Queries. Technical Report DBAI-TR-98/17, available on the web as: http://www.dbai.tuwien.ac.at/staff/gottlob/acyclic.ps, or by email from the authors. An extended abstract concerning part of this work has been published in Proc. of the IEEE Symposium on Foundations of Computer Science (FOCS’98), pp.706–715, Palo Alto, CA, 1998.
G. Gottlob, N. Leone, and F. Scarcello.AComparison of Structural CSP Decomposition Methods. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, pp. 394–399, Stockholm, 1999.
P. Jeavons, D. Cohen, and M. Gyssens. Closure Properties of Constraints. JACM, 44(4), 1997.
Ph. G. Kolaitis and M.Y. Vardi. Conjunctive-Query Containment and Constraint Satisfaction. Proc. of Symp. on Principles of Database Systems (PODS’98), 1998.
C.H. Papadimitriou and M. Yannakakis. On the Complexity of Database Queries. In Proc. of Symp. on Principles of Database Systems (PODS’97), pp.12–19, Tucson, Arizona, 1997.
N. Robertson and P.D. Seymour. Graph Minors II. Algorithmic Aspects of Tree-Width. J. Algorithms, 7:309–322, 1986.
N. Robertson and P.D. Seymour. Graph Minors XX.Wagner’s Conjecture. To appear.
M. Truszczyński. Computing Large and Small Stable Models. In Proc. of the 16th International Conference on Logic Programming (ICLP’99), Las Cruces, New Mexico. To appear.
M. Vardi. Complexity of Relational Query Languages. In Proceedings 14th STOC, pages 137–146, San Francisco, 1982.
M. Yannakakis. Algorithms for Acyclic Database Schemes. In Proc. of Int. Conf. on Very Large Data Bases (VLDB’81), pp. 82–94, C. Zaniolo and C. Delobel Eds., Cannes, France, 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gottlob, G., Scarcello, F., Sideri, M. (1999). Fixed-Parameter Complexity in AI and Nonmonotonic Reasoning. In: Gelfond, M., Leone, N., Pfeifer, G. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 1999. Lecture Notes in Computer Science(), vol 1730. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46767-X_1
Download citation
DOI: https://doi.org/10.1007/3-540-46767-X_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66749-0
Online ISBN: 978-3-540-46767-0
eBook Packages: Springer Book Archive