Counting complexity of propositional abduction. (English) Zbl 1197.68072
Summary: Abduction is an important method of nonmonotonic reasoning with many applications in artificial intelligence and related topics. In this paper, we concentrate on propositional abduction, where the background knowledge is given by a propositional formula. Decision problems of great interest are the existence and the relevance problems. The complexity of these decision problems has been systematically studied while the counting complexity of propositional abduction has remained obscure. The goal of this work is to provide a comprehensive analysis of the counting complexity of propositional abduction in various settings.
Keywords:
computational complexity; counting complexity; propositional abduction; Horn; definite Horn; dual Horn; bijunctive formulasReferences:
| [1] | Bylander, T.; Allemang, D.; Tanner, M. C.; Josephson, J. R., The computational complexity of abduction, Artificial Intelligence, 49, 1-3, 25-60 (1991) · Zbl 0737.68076 |
| [2] | Creignou, N.; Zanuttini, B., A complete classification of the complexity of propositional abduction, SIAM J. Comput., 36, 1, 207-229 (2006) · Zbl 1111.68045 |
| [3] | del Val, A., On some tractable classes in deduction and abduction, Artificial Intelligence, 116, 1-2, 297-313 (2000) · Zbl 0940.03016 |
| [4] | Durand, A.; Hermann, M.; Kolaitis, P. G., Subtractive reductions and complete problems for counting complexity classes, Theoret. Comput. Sci., 340, 3, 496-513 (2005) · Zbl 1077.68033 |
| [5] | Eiter, T.; Gottlob, G., The complexity of logic-based abduction, J. Assoc. Comput. Machinery, 42, 1, 3-42 (1995) · Zbl 0886.68121 |
| [6] | Eiter, T.; Makino, K., On computing all abductive explanations, (Proceedings 18th National Conference on Artificial Intelligence (AAAI 2002). Proceedings 18th National Conference on Artificial Intelligence (AAAI 2002), Edmonton (Alberta, Canada) (2002), AAAI Press), 62-67 |
| [7] | Eiter, T.; Makino, K., Generating all abductive explanations for queries on propositional Horn theories, (Baaz, M.; Makowsky, J. A., Proceedings 12th Annual Conference of the European Association for Computer Science Logic (CSL’03). Proceedings 12th Annual Conference of the European Association for Computer Science Logic (CSL’03), Vienna (Austria). Proceedings 12th Annual Conference of the European Association for Computer Science Logic (CSL’03). Proceedings 12th Annual Conference of the European Association for Computer Science Logic (CSL’03), Vienna (Austria), Lecture Notes in Comput. Sci., vol. 2803 (August 2003), Springer-Verlag), 197-211 · Zbl 1116.68591 |
| [8] | Eshghi, K., A tractable class of abduction problems, (Bajcsy, R., Proceedings 13th International Joint Conference on Artificial Intelligence (IJCAI’93). Proceedings 13th International Joint Conference on Artificial Intelligence (IJCAI’93), Chambéry (France) (1993), Morgan Kaufmann), 3-8 |
| [9] | Fagin, R.; Ullman, J. D.; Vardi, M. Y., On the semantics of updates in databases, (Proceedings 2nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’83). Proceedings 2nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’83), Atlanta (Georgia, USA) (March 1983), Association for Computing Machinery), 352-365 |
| [10] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co. · Zbl 0411.68039 |
| [11] | Gasarch, W. I.; Krentel, M. W.; Rappoport, K. J., OptP as the normal behavior of NP-complete problems, Math. Systems Theory, 28, 6, 487-514 (1995) · Zbl 0830.68064 |
| [12] | Hemaspaandra, L. A.; Vollmer, H., The satanic notations: Counting classes beyond #P and other definitional adventures, SIGACT News, Complex. Theory Column 8, 26, 1, 2-13 (March 1995) |
| [13] | Hermann, M.; Pichler, R., Counting complexity of propositional abduction, (Veloso, M. M., Proceedings 20th International Joint Conference on Artificial Intelligence (IJCAI 2007). Proceedings 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), Hyderabad (India) (January 2007), AAAI Press), 417-422 |
| [14] | Hermann, M.; Pichler, R., Counting complexity of minimal cardinality and minimal weight abduction, (Hölldobler, S.; Lutz, C.; Wansing, H., Proceedings 11th European Conference on Logics in Artificial Intelligence (JELIA 2008). Proceedings 11th European Conference on Logics in Artificial Intelligence (JELIA 2008), Dresden (Germany). Proceedings 11th European Conference on Logics in Artificial Intelligence (JELIA 2008). Proceedings 11th European Conference on Logics in Artificial Intelligence (JELIA 2008), Dresden (Germany), Lecture Notes in Artificial Intelligence, vol. 5293 (2008), Springer-Verlag), 206-218 · Zbl 1178.68562 |
| [15] | Hermann, M.; Pichler, R., Complexity of counting the optimal solutions, Theoret. Comput. Sci., 410, 38-40, 3814-3825 (2009) · Zbl 1171.68011 |
| [16] | Herzig, A.; Lang, J.; Marquis, P.; Polacsek, T., Updates, actions, and planning, (Nebel, B., Proceedings 17th International Joint Conference on Artificial Intelligence (IJCAI 2001). Proceedings 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), Seattle (Washington, USA) (August 2001), Morgan Kaufmann), 119-124 |
| [17] | Kakas, A. C.; Mancarella, P., Database updates through abduction, (McLeod, D.; Sacks-Davis, R.; Schek, H.-J., Proceedings 16th International Conference on Very Large Data Bases (VLDB 1990). Proceedings 16th International Conference on Very Large Data Bases (VLDB 1990), Brisbane (Queensland, Australia) (August 1990), Morgan Kaufmann), 650-661 |
| [18] | Kozen, D. C., The Design and Analysis of Algorithms, Counting Problems and #P (1992), Springer-Verlag, pp. 138-143, Chapter 26 |
| [19] | Krentel, M. W., The complexity of optimization problems, J. Comput. System Sci., 36, 3, 490-509 (1988) · Zbl 0652.68040 |
| [20] | Krentel, M. W., Generalizations of OptP to the polynomial hierarchy, Theoret. Comput. Sci., 97, 2, 183-198 (1992) · Zbl 0769.68031 |
| [21] | Nordh, G.; Zanuttini, B., Propositional abduction is almost always hard, (Kaelbling, L. P.; Saffiotti, A., Proceedings 19th International Joint Conference on Artificial Intelligence (IJCAI 2005). Proceedings 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), Edinburgh (Scotland, UK) (2005), Professional Book Center), 534-539 |
| [22] | Nordh, G.; Zanuttini, B., What makes propositional abduction tractable, Artificial Intelligence, 172, 10, 1245-1284 (2008) · Zbl 1183.68600 |
| [23] | Papatheodorou, I.; Kakas, A. C.; Sergot, M. J., Inference of gene relations from microarray data by abduction, (Baral, Ch.; Greco, G.; Leone, N.; Terracina, G., Proceedings 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2005). Proceedings 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2005), Diamante (Italy). Proceedings 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2005). Proceedings 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2005), Diamante (Italy), Lecture Notes in Comput. Sci., vol. 3662 (September 2005), Springer-Verlag), 389-393 · Zbl 1152.68417 |
| [24] | Peng, Y.; Reggia, J. A., Abductive Inference Models for Diagnostic Problem Solving (1990), Springer-Verlag · Zbl 0723.68096 |
| [25] | Poole, D., Probabilistic Horn abduction and Bayesian networks, Artificial Intelligence, 64, 1, 81-129 (1993) · Zbl 0792.68176 |
| [27] | Selman, B.; Levesque, H. J., Abductive and default reasoning: A computational core, (Proceedings 8th National Conference on Artificial Intelligence. Proceedings 8th National Conference on Artificial Intelligence, Boston (Massachusetts, USA) (1990), MIT Press), 343-348 |
| [28] | Valiant, L. G., The complexity of computing the permanent, Theoret. Comput. Sci., 8, 2, 189-201 (1979) · Zbl 0415.68008 |
| [29] | Valiant, L. G., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 3, 410-421 (1979) · Zbl 0419.68082 |
| [30] | Zanuttini, B., New polynomial classes for logic-based abduction, J. Artificial Intelligence Res., 19, 1-10 (2003) · Zbl 1026.68122 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
