The complexity of Bayesian networks specified by propositional and relational languages. (English) Zbl 1451.68257
Summary: We examine the complexity of inference in Bayesian networks specified by logical languages. We consider representations that range from fragments of propositional logic to function-free first-order logic with equality; in doing so we cover a variety of plate models and of probabilistic relational models. We study the complexity of inferences when network, query and domain are the input (the inferential and the combined complexity), when the network is fixed and query and domain are the input (the query/data complexity), and when the network and query are fixed and the domain is the input (the domain complexity). We draw connections with probabilistic databases and liftability results, and obtain complexity classes that range from polynomial to exponential levels; we identify new languages with tractable inference, and we relate our results to languages based on plates and probabilistic relational models.
MSC:
| 68T27 | Logic in artificial intelligence |
| 62H22 | Probabilistic graphical models |
| 68P15 | Database theory |
Keywords:
Bayesian networks; complexity theory; relational logic; plate models; probabilistic relational modelsReferences:
| [1] | Artale, A.; Calvanese, D.; Kontchakov, R.; Zakharyashev, M., The DL-Lite family and relations, J. Artif. Intell. Res., 36, 1-69 (2009) · Zbl 1192.68657 |
| [2] | Baader, F., Terminological cycles in a description logic with existential restrictions, (IJCAI (2003)), 325-330 |
| [3] | Baader, F.; Nutt, W., Basic description logics, (Description Logic Handbook (2002), Cambridge University Press), 47-100 |
| [4] | Bacchus, F., Representing and Reasoning with Probabilistic Knowledge: A Logical Approach (1990), MIT Press: MIT Press Cambridge |
| [5] | Bacchus, F., Using first-order probability logic for the construction of Bayesian networks, (Conference on Uncertainty in Artificial Intelligence (1993)), 219-226 |
| [6] | Bailey, D. D.; Dalmau, V.; Kolaitis, P. G., Phase transitions of PP-complete satisfiability problems, Discrete Appl. Math., 155, 1627-1639 (2007) · Zbl 1123.68117 |
| [7] | Bauland, M.; Bohler, E.; Creignou, N.; Reith, S.; Schnoor, H.; Vollmer, H., The complexity of problems for quantified constraints, Theory Comput. Syst., 47, 454-490 (2010) · Zbl 1204.68182 |
| [8] | Beame, P.; Van den Broeck, G.; Gribkoff, E.; Suciu, D., Symmetric weighted first-order model counting, (ACM Symposium on Principles of Database Systems. ACM Symposium on Principles of Database Systems, PODS (2015)) |
| [9] | Benjelloun, O.; Sarma, A. D.; Halevy, A.; Theobald, M.; Widom, J., Databases with uncertainty and lineage, Int. J. VLDB, 17, 2, 243-264 (2008) |
| [10] | Blei, D. M.; Ng, A. Y.; Jordan, M. I., Latent Dirichlet allocation, J. Mach. Learn. Res., 3, 993-1022 (2003) · Zbl 1112.68379 |
| [11] | Bubley, R.; Dyer, M., Graph orientations with no sink and an approximation for a hard case of #SAT, (ACM-SIAM Symposium on Discrete Algorithms (1997)), 248-257 · Zbl 1321.68378 |
| [12] | Buchman, D.; Poole, D., Negative probabilities in probabilistic logic programs, Int. J. Approx. Reason., 83, 43-59 (2017) · Zbl 1404.68034 |
| [13] | Buchman, D.; Poole, D., Why rules are complex: real-valued probabilistic logic programs are not fully expressive, (Conference on Uncertainty in Artificial Intelligence (2017)) |
| [14] | Buhrman, H.; Fortnow, L.; Thierauf, T., Nonrelativizing separations, (Proceedings of IEEE Complexity (1998)), 8-12 · Zbl 0935.68032 |
| [15] | Bulatov, A.; Dyer, M.; Goldberg, L. A.; Jalsenius, M.; Jerrum, M.; Richerby, D., The complexity of weighted and unweighted \(\# CSP\), J. Comput. Syst. Sci., 78, 681-688 (2012) · Zbl 1282.68110 |
| [16] | Buntine, W. L., Operations for learning with graphical models, J. Artif. Intell. Res., 2, 159-225 (1994) |
| [17] | Cai, J.-Y.; Lu, P.; Xia, M., Holographic reduction, interpolation and hardness, Comput. Complex., 21, 4, 573-604 (2012) · Zbl 1282.68120 |
| [18] | Calvanese, D.; Giacomo, G. D.; Lembo, D.; Lenzerini, M.; Rosati, R., DL-Lite: tractable description logics for ontologies, (AAAI (2005)), 602-607 |
| [19] | Calvanese, D.; Giacomo, G. D.; Lembo, D.; Lenzerini, M.; Rosati, R., Data complexity of query answering in description logics, (Knowledge Representation (2006)), 260-270 |
| [20] | Carvalho, R. N.; Laskey, K. B.; Costa, P. C., PR-OWL 2.0—bridging the gap to OWL semantics, (URSW 2008-2010/UniDL 2010. URSW 2008-2010/UniDL 2010, LNAI, vol. 7123 (2013)), 1-18 |
| [21] | Ceylan, I. I.; Peñaloza, R., The Bayesian description logic \(BEL\), (International Joint Conference on Automated Reasoning (2014)), 480-494 · Zbl 1409.68277 |
| [22] | Chavira, M.; Darwiche, A., On probabilistic inference by weighted model counting, Artif. Intell., 172, 6-7, 772-799 (2008) · Zbl 1182.68297 |
| [23] | Costa, P. C.G.; Laskey, K. B., PR-OWL: a framework for probabilistic ontologies, (Conference on Formal Ontology in Information Systems (2006)) |
| [24] | Costa, V. S.; Page, D.; Qazi, M.; Cussens, J., CLP \((BN)\): constraint logic programming for probabilistic knowledge, (Kjaerulff, U.; Meek, C., Conference on Uncertainty in Artificial Intelligence (2003), Morgan-Kaufmann), 517-524 |
| [25] | Cozman, F. G.; Mauá, D. D., Bayesian networks specified using propositional and relational constructs: combined, data, and domain complexity, (AAAI Conference on Artificial Intelligence (2015)) |
| [26] | Cozman, F. G.; Mauá, D. D., On the semantics and complexity of probabilistic logic programs, J. Artif. Intell. Res., 60, 221-262 (2017) · Zbl 1418.68027 |
| [27] | Cozman, F. G.; Polastro, R. B., Complexity analysis and variational inference for interpretation-based probabilistic description logics, (Proceedings of the Conference on Uncertainty in Artificial Intelligence (2009), AUAI Press), 117-125 |
| [28] | Dalvi, N.; Suciu, D., Efficient query evaluation on probabilistic databases, VLDB J., 16, 523-544 (2007) |
| [29] | Dalvi, N.; Suciu, D., The dichotomy of probabilistic inference for unions of conjunctive queries, J. ACM., 59, 6, 30:1-30:87 (2012) · Zbl 1281.68095 |
| [30] | d’Amato, C.; Fanizzi, N.; Lukasiewicz, T., Tractable reasoning with Bayesian description logics, (International Conference on Scalable Uncertainty Management (2008)), 146-159 |
| [31] | Darviche, A.; Provan, G., Query DAGSs: a practical paradigm for implementing belief-network inference, (Horvitz, E.; Jensen, F., Conference on Uncertainty in Artificial Intelligence (1996), Morgan Kaufmann), 203-210 |
| [32] | Darwiche, A., A differential approach to inference in Bayesian networks, J. ACM., 50, 3, 280-305 (2003) · Zbl 1325.68226 |
| [33] | Darwiche, A., Modeling and Reasoning with Bayesian Networks (2009), Cambridge University Press · Zbl 1231.68003 |
| [34] | Darwiche, A.; Marquis, P., A knowledge compilation map, J. Artif. Intell. Res., 17, 229-264 (2002) · Zbl 1045.68131 |
| [35] | De Bona, G.; Cozman, F. G., On the coherence of probabilistic relational formalisms, Entropy, 20, 229/1-229/24 (2018) |
| [36] | Ding, Z.; Peng, Y.; Pan, R., BayesOWL: uncertainty modeling in semantic web ontologies, (Soft Computing in Ontologies and Semantic Web. Soft Computing in Ontologies and Semantic Web, Studies in Fuzziness and Soft Computing, vol. 204 (2006), Springer: Springer Berlin/Heidelberg), 3-29 · Zbl 1138.68323 |
| [37] | Domingos, P.; Webb, W. A., A tractable first-order probabilistic logic, (AAAI (2012)), 1902-1909 |
| [38] | Durand, A.; Hermann, M.; Kolaitis, P. G., Subtractive reductions and complete problems for counting complexity classes, Theor. Comput. Sci., 340, 3, 496-513 (2005) · Zbl 1077.68033 |
| [39] | Fierens, D.; Blockeel, H.; Bruynooghe, M.; Ramon, J., Logical Bayesian networks and their relation to other probabilistic logical models, (Int. Conference on Inductive Logic Programming (2005)), 121-135 · Zbl 1134.68507 |
| [40] | Fierens, D.; Blockeel, H.; Ramon, J.; Bruynooghe, M., Logical Bayesian networks, (Workshop on Multi-Relational Data Mining (2004)), 19-30 |
| [41] | Fierens, D.; Van den Broeck, G.; Renkens, J.; Shrerionov, D.; Gutmann, B.; Janssens, G.; de Raedt, L., Inference and learning in probabilistic logic programs using weighted Boolean formulas, Theory Pract. Log. Program., 15, 3, 358-401 (2014) · Zbl 1379.68062 |
| [42] | Flum, J.; Grohe, M., The parameterized complexity of counting problems, SIAM J. Comput., 33, 4, 892-922 (2004) · Zbl 1105.68042 |
| [43] | Friedman, N.; Getoor, L.; Koller, D.; Pfeffer, A., Learning probabilistic relational models, (International Joint Conference on Artificial Intelligence (1999)), 1300-1309 |
| [44] | Getoor, L.; Friedman, N.; Koller, D.; Pfeffer, A.; Taskar, B., Probabilistic relational models, (Introduction to Statistical Relational Learning (2007)) · Zbl 1141.68054 |
| [45] | Getoor, L.; Grant, J., PRL: a probabilistic relational language, Mach. Learn., 62, 7-31 (2006) · Zbl 1470.68222 |
| [46] | Getoor, L.; Taskar, B., Introduction to Statistical Relational Learning (2007), MIT Press · Zbl 1141.68054 |
| [47] | Gilks, W.; Thomas, A.; Spiegelhalter, D., A language and program for complex Bayesian modelling, Statistician, 43, 169-178 (1993) |
| [48] | Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6, 4, 675-695 (1977) · Zbl 0366.02024 |
| [49] | Glesner, S.; Koller, D., Constructing flexible dynamic belief networks from first-order probabilistic knowledge bases, (Symbolic and Quantitative Approaches to Reasoning with Uncertainty (1995)), 217-226 |
| [50] | Goldman, R. P.; Charniak, E., Dynamic construction of belief networks, (Conference of Uncertainty in Artificial Intelligence (1990)), 90-97 |
| [51] | Goldsmith, J.; Hagen, M.; Mundhenk, M., Complexity of DNF minimization and isomorphism testing for monotone formulas, Inf. Comput., 206, 6, 760-775 (2008) · Zbl 1152.68021 |
| [52] | Grädel, E., Finite model theory and descriptive complexity, (Finite Model Theory and its Applications (2007), Springer), 125-229 |
| [53] | Gribkoff, E.; Van den Broeck, G.; Suciu, D., Understanding the complexity of lifted inference and asymmetric weighted model counting, (Conference on Uncertainty in Artificial Intelligence (2014)) |
| [54] | Grove, A.; Halpern, J.; Koller, D., Asymptotic conditional probabilities: the unary case, SIAM J. Comput., 25, 1, 1-51 (1996) · Zbl 0848.03004 |
| [55] | Haddawy, P., Generating Bayesian networks from probability logic knowledge, (Conference on Uncertainty in Artificial Intelligence (1994)), 262-269 |
| [56] | Halpern, Joseph Y., Reasoning About Uncertainty (2003), MIT Press · Zbl 1090.68105 |
| [57] | Heckerman, D., An empirical comparison of three inference methods, (Shachter, R. D.; Kanal, L. N.; Lemmer, J. F., Uncertainty in Artificial Intelligence, vol. 4 (1990), Elsevier Science Publishers: Elsevier Science Publishers North-Holland), 283-303 |
| [58] | Heckerman, D.; Meek, C.; Koller, D., Probabilistic entity-relationship models, PRMs, and plate models, (Getoor, L.; Taskar, B., Introduction to Statistical Relational Learning (2007), MIT Press), 201-238 |
| [59] | Horsch, M. C.; Poole, D., A dynamic approach to probabilistic inference using Bayesian networks, (Conference of Uncertainty in Artificial Intelligence (1990)), 155-161 |
| [60] | Jaeger, M., Relational Bayesian networks, (Geiger, D.; Shenoy, P. P., Conference on Uncertainty in Artificial Intelligence (1997), Morgan Kaufmann: Morgan Kaufmann San Francisco, California), 266-273 |
| [61] | Jaeger, M., Complex probabilistic modeling with recursive relational Bayesian networks, Ann. Math. Artif. Intell., 32, 179-220 (2001) · Zbl 1314.68302 |
| [62] | Jaeger, M., Probabilistic role models and the guarded fragment, (Information Processing and Management of Uncertainty in Knowledge-Based Systems. Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU (2004)), 235-242 |
| [63] | Jaeger, M., Lower complexity bounds for lifted inference, Theory Pract. Log. Program., 15, 2, 246-264 (2015) · Zbl 1379.68298 |
| [64] | Jaeger, M.; Van Den Broeck, G., Liftability of probabilistic inference: upper and lower bounds, (2nd Statistical Relational AI. 2nd Statistical Relational AI, (StaRAI-12) Workshop (2012)) |
| [65] | Kazemi, S. M.; Kimmig, A.; Van den Broeck, G.; Poole, D., New liftable classes for first-order probabilistic inference, (NIPS (2016)) |
| [66] | Kersting, K., Lifted probabilistic inference, (Raedt, L. D.; Bessiere, C.; Dubois, D.; Doherty, P.; Frasconi, P.; Heintz, F.; Lucas, P., European Conference on Artificial Intelligence (2012), IOS Press) |
| [67] | Kersting, K.; Raedt, L. D.; Kramer, S., Interpreting Bayesian logic programs, (AAAI-2000 Workshop on Learning Statistical Models from Relational Data (2000)) |
| [68] | Koch, C., MayBMS: a system for managing large uncertain and probabilistic databases, (Aggarwal, C. C., Managing and Mining Uncertain Data (2009), Springer-Verlag), 149-184 · Zbl 1185.68271 |
| [69] | Koller, D.; Friedman, N., Probabilistic Graphical Models: Principles and Techniques (2009), MIT Press · Zbl 1183.68483 |
| [70] | Koller, D.; Levy, A. Y.; Pfeffer, A., P-CLASSIC: a tractable probabilistic description logic, (AAAI (1997)), 390-397 |
| [71] | Koller, D.; Pfeffer, A., Object-oriented Bayesian networks, (Conference on Uncertainty in Artificial Intelligence (1997)), 302-313 |
| [72] | Koller, D.; Pfeffer, A., Probabilistic frame-based systems, (National Conference on Artificial Intelligence. National Conference on Artificial Intelligence, AAAI (1998)), 580-587 |
| [73] | Kwisthout, J., The Computational Complexity of Probabilistic Inference (2011), Radboud University Nijmegen: Radboud University Nijmegen The Netherlands, Tech. Rep. ICIS-R11003 |
| [74] | Kwisthout, J. H.P.; Bodlaender, H. L.; der Gaag, L. V., The necessity of bounded treewidth for efficient inference in Bayesian networks, (European Conference on Artificial Intelligence (2010)), 237-242 · Zbl 1211.68275 |
| [75] | Ladner, R. E., Polynomial space counting problems, SIAM J. Comput., 18, 6, 1087-1097 (1989) · Zbl 0692.68036 |
| [76] | Laskey, K. B., MEBN: a language for first-order Bayesian knowledge bases, Artif. Intell., 172, 2-3, 140-178 (2008) · Zbl 1182.68288 |
| [77] | Lewis, H. R., Complexity results for classes of quantificational formulas, J. Comput. Syst. Sci., 21, 317-353 (1980) · Zbl 0471.03034 |
| [78] | Libkin, L., Elements of Finite Model Theory (2004), Springer · Zbl 1060.03002 |
| [79] | Lin, C.; Liu, J.; Lu, P., A simple FPTAS for counting edge covers, (ACM-SIAM Symposium on Discrete Algorithms (2014)), 341-348 · Zbl 1422.68303 |
| [80] | Liu, J.; Lu, P.; Zhang, C., FPTAS for counting weighted edge covers, (European Symposium on Algorithms (2014)), 654-665 · Zbl 1425.68457 |
| [81] | Lukasiewicz, T.; Straccia, U., Managing uncertainty and vagueness in description logics for the semantic web, J. Web Semant., 6, 291-308 (2008) |
| [82] | Lunn, D.; Jackson, C.; Best, N.; Thomas, A.; Spiegelhalter, D., The BUGS Book: A Practical Introduction to Bayesian Analysis (2012), CRC Press/Chapman and Hall |
| [83] | Lunn, D.; Spiegelhalter, D.; Thomas, A.; Best, N., The BUGS project: evolution, critique and future directions, Stat. Med., 28, 3049-3067 (2009) |
| [84] | Mahoney, S.; Laskey, K. B., Network engineering for complex belief networks, (Conference on Uncertainty in Artificial Intelligence (1996)) |
| [85] | Mansinghka, V.; Radul, A., CoreVenture: a highlevel, reflective machine language for probabilistic programming, (NIPS Workshop on Probabilistic Programming (2014)) |
| [86] | Mauá, D. D.; Cozman, F. G., The effect of combination functions on the complexity of relational Bayesian networks, Int. J. Approx. Reason., 85, 178-195 (2017) · Zbl 1419.68172 |
| [87] | Mauá, D. D.; de Campos, C. P.; Cozman, F. G., The complexity of MAP inference in Bayesian networks specified through logical languages, (International Joint Conference on Artificial Intelligence (2015)), 889-895 |
| [88] | Mauá, D. D.; Cozman, F. G., A tractable class of model counting problems, (Encontro Nacional de Inteligência Artificial (2015)) |
| [89] | Milch, B.; Marthi, B.; Sontag, D.; Russell, S.; Ong, D. L.; Kolobov, A., BLOG: probabilistic models with unknown objects, (IJCAI (2005)) |
| [90] | Milch, B.; Zettlemoyer, L. S.; Kersting, K.; Haimes, M.; Kaelbling, L. P., Lifted probabilistic inference with counting formulas, (AAAI (2008)), 1062-1068 |
| [91] | Mitchell, T.; Cohen, W.; Hruschka, E.; Talukdar, P.; Betteridge, J.; Carlson, A.; Dalvi, B.; Gardner, M.; Kisiel, B.; Krishnamurthy, J.; Lao, N.; Mazaitis, K.; Mohamed, T.; Nakashole, N.; Platanios, E.; Ritter, A.; Samadi, M.; Settles, B.; Wang, R.; Wijaya, D.; Gupta, A.; Chen, X.; Saparov, A.; Greaves, M.; Welling, J., Never-ending learning, (Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI-15 (2015)) |
| [92] | Neapolitan, R. E., Learning Bayesian Networks (2003), Prentice Hall |
| [93] | Ngo, L.; Haddawy, P., Answering queries from context-sensitive probabilistic knowledge bases, Theor. Comput. Sci., 171, 1-2, 147-177 (1997) · Zbl 0874.68280 |
| [94] | Niepert, M.; Van den Broeck, G., Tractability through exchangeability: a new perspective on efficient probabilistic inference, (AAAI Conference on Artificial Intelligence (2014)), 2467-2475 |
| [95] | Ogiwara, M., A complexity theory for feasible closure properties, J. Comput. Syst. Sci., 46, 295-325 (1993) · Zbl 0798.68060 |
| [96] | Papadimitriou, C. H., A note on succinct representations of graphs, Inf. Control, 71, 181-185 (1986) · Zbl 0616.68041 |
| [97] | Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley Publishing · Zbl 0833.68049 |
| [98] | Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, California |
| [99] | Pearl, J., Causality: Models, Reasoning, and Inference (2009), Cambridge University Press: Cambridge University Press Cambridge, United Kingdom · Zbl 1188.68291 |
| [100] | Pfeffer, A., IBAL: a probabilistic rational programming language, (International Joint Conference on Artificial Intelligence (2001)), 733-740 |
| [101] | Poole, D., Probabilistic Horn abduction and Bayesian networks, Artif. Intell., 64, 81-129 (1993) · Zbl 0792.68176 |
| [102] | Poole, D., The independent choice logic for modelling multiple agents under uncertainty, Artif. Intell., 94, 1/2, 7-56 (1997) · Zbl 0902.03017 |
| [103] | Poole, D., First-order probabilistic inference, (International Joint Conference on Artificial Intelligence. International Joint Conference on Artificial Intelligence, IJCAI (2003)), 985-991 |
| [104] | Poole, D., The independent choice logic and beyond, (Raedt, L. D.; Frasconi, P.; Kersting, K.; Muggleton, S., Probabilistic Inductive Logic Programming. Probabilistic Inductive Logic Programming, Lecture Notes in Computer Science, vol. 4911 (2008), Springer), 222-243 · Zbl 1137.68596 |
| [105] | Poole, D., Probabilistic programming languages: independent choices and deterministic systems, (Dechter, R.; Geffner, H.; Halpern, J. Y., Heuristics, Probability and Causality—A Tribute to Judea Pearl (2010), College Publications), 253-269 · Zbl 1216.68070 |
| [106] | Poon, H.; Domingos, P., Sum-product networks: a new deep architecture, (Conference on Uncertainty in Artificial Intelligence (2011)) |
| [107] | Pourret, O.; Naim, P.; Marcot, B., Bayesian Networks—A Practical Guide to Applications (2008), Wiley · Zbl 1275.62010 |
| [108] | Provan, J. S.; Ball, M. O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput., 12, 4, 777-788 (1983) · Zbl 0524.68041 |
| [109] | Raedt, L. D., Logical and Relational Learning (2008), Springer · Zbl 1203.68145 |
| [110] | Raedt, L. D.; Kersting, K., Probabilistic inductive logic programming, (International Conference on Algorithmic Learning Theory (2004)), 19-36 · Zbl 1110.68392 |
| [111] | Ramachandran, R.; Qi, G.; Wang, K.; Wang, J.; Thornton, J., Probabilistic reasoning in DL-Lite, (Pacific Rim International Conference on Trends in Artificial Intelligence (2012)), 480-491 |
| [112] | Riguzzi, F., The distribution semantics is well-defined for all normal programs, (Riguzzi, F.; Vennekens, J., International Workshop on Probabilistic Logic Programming. International Workshop on Probabilistic Logic Programming, CEUR Workshop Proc., vol. 1413 (2015)), 69-84 |
| [113] | Roth, D., On the hardness of approximate reasoning, Artif. Intell., 82, 1-2, 273-302 (1996) · Zbl 1506.68143 |
| [114] | Sanner, S.; McAllester, D., Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference, (International Joint Conference on Artificial Intelligence (2005)), 1384-1390 |
| [115] | Sato, T., A statistical learning method for logic programs with distribution semantics, (Int. Conference on Logic Programming (1995)), 715-729 |
| [116] | Sato, T.; Kameya, Y., Parameter learning of logic programs for symbolic-statistical modeling, J. Artif. Intell. Res., 15, 391-454 (2001) · Zbl 0994.68025 |
| [117] | Simon, J., On Some Central Problems in Computational Complexity (1975), Department of Computer Science, Cornell University, Tech. Rep. TR75-224 |
| [118] | Singh, S.; Mayfield, C.; Mittal, S.; Prabhakar, S.; Hambrusch, S.; Shah, R., Orion 2.0: native support for uncertain data, (SIGMOD (2008)), 1239-1241 |
| [119] | Sommestad, T.; Ekstedt, M.; Johnson, P., A probabilistic relational model for security risk analysis, Comput. Secur., 29, 659-679 (2010) |
| [120] | Sontag, D.; Roy, D., Complexity of inference in latent Dirichlet allocation, (Advances in Neural Information Processing Systems, vol. 24 (2011)), 1008-1016 |
| [121] | Suciu, D.; Oiteanu, D.; Ré, C.; Koch, C., Probabilistic Databases (2011), Morgan & Claypool Publishers · Zbl 1237.68012 |
| [122] | Taghipour, N.; Fierens, D.; Van den Broeck, G.; Davis, J.; Blockeel, H., Completeness results for lifted variable elimination, (Conference on Artificial Intelligence and Statistics. Conference on Artificial Intelligence and Statistics, AISTATS, Scottsdale, USA (2013)), 572-580 |
| [123] | Tenorth, M.; Beetz, M., KnowRob: a knowledge processing infrastructure for cognition-enabled robots, Int. J. Robot. Res., 32, 5, 566-590 (2013) |
| [124] | Tobies, S., The complexity of reasoning with cardinality restrictions and nominals in expressive description logics, J. Artif. Intell. Res., 12, 199-217 (2000) · Zbl 0941.03029 |
| [125] | Toda, S., PP is as hard as the polynomial-time hierarchy, SIAM J. Sci. Comput., 20, 5, 865-877 (1991) · Zbl 0733.68034 |
| [126] | Toda, S.; Watanabe, O., Polynomial-time 1-Turing reductions from #PH to #P, Theor. Comput. Sci., 100, 205-221 (1992) · Zbl 0779.68037 |
| [127] | Tóran, J., Complexity classes defined by counting quantifiers, J. ACM, 38, 3, 753-774 (1991) · Zbl 0799.68080 |
| [128] | Vadhan, S. P., The complexity of counting in sparse, regular and planar graphs, SIAM J. Sci. Comput., 31, 2, 398-427 (2001) · Zbl 0994.68070 |
| [129] | Valiant, L. G., The complexity of computing the permanent, Theor. Comput. Sci., 8, 189-201 (1979) · Zbl 0415.68008 |
| [130] | Valiant, L. G., The complexity of enumeration and reliability problems, SIAM J. Sci. Comput., 8, 3, 410-421 (1979) · Zbl 0419.68082 |
| [131] | Valiant, L. G., Accidental algorithms, (Annual IEEE Symposium on Foundations of Computer Science (2006)), 509-517 |
| [132] | Van den Broeck, G., On the completeness of first-order knowledge compilation for lifted probabilistic inference, (Neural Processing Information Systems (2011)), 1386-1394 |
| [133] | Van den Broeck, G.; Davis, J., Conditioning in first-order knowledge compilation and lifted probabilistic inference, (AAAI Conference on Artificial Intelligence (2012)), 1961-1967 |
| [134] | Van den Broeck, G.; Wannes, M.; Darwiche, A., Skolemization for weighted first-order model counting, (International Conference on Principles of Knowledge Representation and Reasoning (2014)), 111-120 |
| [135] | Vardi, M. Y., The complexity of relational query languages, (Annual ACM Symposium on Theory of Computing (1982)), 137-146 |
| [136] | Wagner, K. W., The complexity of combinatorial problems with succinct input representation, Acta Inform., 23, 325-356 (1986) · Zbl 0621.68032 |
| [137] | Wang, D. Z.; Michelaks, E.; Garofalakis, M.; Hellerstein, J. M., BayesStore: managing large, uncertain data repositories with probabilistic graphical models, VLDB Endow., 1, 340-351 (2008) |
| [138] | Wellman, M. P.; Breese, J. S.; Goldman, R. P., From knowledge bases to decision models, Knowl. Eng. Rev., 7, 1, 35-53 (1992) |
| [139] | Widom, J., Trio: a system for data, uncertainty, and lineage, (Aggarwal, C. C., Managing and Mining Uncertain Data (2009), Springer-Verlag), 113-148 |
| [140] | Xia, M.; Zhao, W., #3-regular bipartite planar vertex cover is #P-complete, (Theory and Applications of Models of Computation. Theory and Applications of Models of Computation, Theoretical Computer Science and General Issues, vol. 3959 (2006)), 356-364 · Zbl 1178.68286 |
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.
