Parameterized complexity of theory of mind reasoning in dynamic epistemic logic. (English) Zbl 1509.03067
Summary: Theory of mind refers to the human capacity for reasoning about others’ mental states based on observations of their actions and unfolding events. This type of reasoning is notorious in the cognitive science literature for its presumed computational intractability. A possible reason could be that it may involve higher-order thinking (e.g., ‘you believe that I believe that you believe’). To investigate this, we formalize theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameterize ‘order of thinking’. We prove that theory of mind reasoning, so formalized, indeed is intractable (specifically, PSPACE-complete). Using parameterized complexity we prove, however, that the ‘order parameter’ is not a source of intractability. We furthermore consider a set of alternative parameters and investigate which of them are sources of intractability. We discuss the implications of these results for the understanding of theory of mind.
MSC:
| 03B42 | Logics of knowledge and belief (including belief change) |
| 68Q27 | Parameterized complexity, tractability and kernelization |
Keywords:
theory of mind; higher-order reasoning; computational-level analysis; dynamic epistemic logic; parameterized complexity; intractabilityReferences:
| [1] | Apperly, I. (2011). Mindreaders: The cognitive basis of “Theory of Mind”. Hove: Psychology Press. |
| [2] | Arkoudas, K., & Bringsjord, S. (2009). Propositional attitudes and causation. International Journal of Software and Informatics, 3(1), 47-65. |
| [3] | Arora, S., & Barak, B. (2009). Computational complexity: A modern approach. Cambridge: Cambridge University Press. · Zbl 1193.68112 · doi:10.1017/CBO9780511804090 |
| [4] | Arslan, B., Taatgen, N., & Verbrugge, R. (2013). Modeling developmental transitions in reasoning about false beliefs of others. In Proceedings of the 12th international conference on cognitive modeling (pp. 77-82), Ottawa: Carleton University. |
| [5] | Aucher, G. (2010). An internal version of epistemic logic. Studia Logica, 94(1), 1-22. · Zbl 1200.03016 · doi:10.1007/s11225-010-9227-9 |
| [6] | Aucher, G., & Schwarzentruber, F. (2013). On the complexity of dynamic epistemic logic. In Proceedings of the fourteenth conference on theoretical aspects of rationality and knowledge (TARK). |
| [7] | Baker, C. L. (2012). Bayesian theory of mind: Modeling human reasoning about beliefs, desires, goals, and social relations. Ph.D. thesis, Massachusetts Institute of Technology. |
| [8] | Baltag, A., Moss, LS., & Solecki, S. (1998). The logic of public announcements, common knowledge, and private suspicions. In Proceedings of the 7th conference on theoretical aspects of rationality and knowledge (TARK). · Zbl 1386.03019 |
| [9] | Baron-Cohen, S., Leslie, A. M., & Frith, U. (1985). Does the autistic child have a theory of mind? Cognition, 21(1), 37-46. · doi:10.1016/0010-0277(85)90022-8 |
| [10] | Barton, E. G., Berwick, R., & Ristad, E. S. (1987). Computational Complexity and Natural Language. The MIT Press: Bradford Books. |
| [11] | Blokpoel, M., Kwisthout, J., van der Weide, T. P., Wareham, T., & van Rooij, I. (2013). A computational-level explanation of the speed of goal inference. Journal of Mathematical Psychology, 57(3), 117-133. · Zbl 1284.91499 · doi:10.1016/j.jmp.2013.05.006 |
| [12] | Bolander, T. (2014). Seeing is believing: Formalising false-belief tasks in dynamic epistemic logic. In European conference on social intelligence (ECSI 2014) (pp. 87-107). |
| [13] | Bolander, T., & Andersen, M. B. (2011). Epistemic planning for single and multi-agent systems. Journal of Applied Non-Classical Logics, 21(1), 9-34. · Zbl 1242.68285 · doi:10.3166/jancl.21.9-34 |
| [14] | Bolander, T., Jensen, M. H., & Schwarzentruber, F. (2015). Complexity results in epistemic planning. In Proceedings of the 24th international joint conference on artificial intelligence (IJCAI), AAAI Press/IJCAI. |
| [15] | Braüner, T. (2014). Hybrid-logical reasoning in the smarties and Sally-Anne tasks. Journal of Logic, Language and Information, 23(4), 415-439. https://doi.org/10.1007/s10849-014-9206-z. · Zbl 1306.03010 · doi:10.1007/s10849-014-9206-z |
| [16] | Burke, K., Demaine, E. D., Gregg, H., Hearn, R. A., Hesterberg, A., Hoffmann, M., Ito, H., Kostitsyna, I., Leonard, J., & Löffler, M., et al. (2015). Single-player and two-player buttons and scissors games. In Japanese conference on discrete and computational geometry and graphs (JCDCGG 2015), Lecture Notes in Computer Science (Vol. 9943, pp. 60-72). Belrin: Springer. · Zbl 1482.68106 |
| [17] | Bylander, T. (1994). The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2), 165-204. · Zbl 0821.68065 · doi:10.1016/0004-3702(94)90081-7 |
| [18] | Carruthers, P. (2006). The architecture of the mind. Oxford: Oxford University Press. · doi:10.1093/acprof:oso/9780199207077.001.0001 |
| [19] | Cherniak, C. (1990). Minimal rationality. Cambridge: MIT Press. |
| [20] | Cook, S. A. (1971). The complexity of theorem proving procedures. In Proceedings of the 3rd annual ACM symposium on the theory of computing (STOC 1971) (pp. 151-158), New York. · Zbl 0253.68020 |
| [21] | Cummins, R. (2000). “How does it work?” versus “What are the laws?”: Two conceptions of psychological explanation. In F. Keil & Robert A. Wilson (Eds.), Explanation and cognition (pp. 117-145). Cambridge, MA: MIT Press. |
| [22] | Dégremont, C., Kurzen, L., & Szymanik, J. (2014). Exploring the tractability border in epistemic tasks. Synthese, 191(3), 371-408. · Zbl 1310.03022 · doi:10.1007/s11229-012-0215-7 |
| [23] | Deineko, V. G., Hoffmann, M., Okamoto, Y., & Woeginger, G. J. (2006). The traveling salesman problem with few inner points. Operations Research Letters, 34(1), 106-110. https://doi.org/10.1016/j.orl.2005.01.002. · Zbl 1080.90064 · doi:10.1016/j.orl.2005.01.002 |
| [24] | Downey, R. G., & Fellows, M. R. (1999). Parameterized complexity. Monographs in computer science. New York: Springer. · doi:10.1007/978-1-4612-0515-9 |
| [25] | Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Texts in computer science. Berlin: Springer. · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1 |
| [26] | Fellows, M. R., Hermelin, D., Rosamond, F. A., & Vialette, S. (2009). On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1), 53-61. · Zbl 1161.68038 · doi:10.1016/j.tcs.2008.09.065 |
| [27] | Flobbe, L., Verbrugge, R., Hendriks, P., & Krämer, I. (2008). Children’s application of theory of mind in reasoning and language. Journal of Logic, Language and Information, 17(4), 417-442. · Zbl 1157.91441 · doi:10.1007/s10849-008-9064-7 |
| [28] | Flum, J., & Grohe, M. (2003). Describing parameterized complexity classes. Information and Computation, 187(2), 291-319. · Zbl 1076.68031 · doi:10.1016/S0890-5401(03)00161-5 |
| [29] | Flum, J., & Grohe, M. (2006). Parameterized complexity theory, Texts in theoretical computer science. In An EATCS Series (vol. XIV). Berlin: Springer. · Zbl 1143.68016 |
| [30] | Fortnow, L. (2009). The status of the P versus NP problem. Communications of the ACM, 52(9), 78-86. · doi:10.1145/1562164.1562186 |
| [31] | Frith, U. (2001). Mind blindness and the brain in autism. Neuron, 32(6), 969-979. · doi:10.1016/S0896-6273(01)00552-9 |
| [32] | Frixione, M. (2001). Tractable competence. Minds and Machines, 11(3), 379-397. · Zbl 0972.68690 · doi:10.1023/A:1017503201702 |
| [33] | Garey, M. R., & Johnson, D. R. (1979). Computers and Intractability. San Francisco: WH Freeman. · Zbl 0411.68039 |
| [34] | Gasarch, W. I. (2012). Guest column: the second P =? NP poll. SIGACT News, 43(2), 53-77. · doi:10.1145/2261417.2261434 |
| [35] | Gierasimczuk, N., & Szymanik, J. (2011). A note on a generalization of the muddy children puzzle. In Proceedings of the 13th conference on theoretical aspects of rationality and knowledge (TARK). · Zbl 1348.68258 |
| [36] | Haselager, W. F. G. (1997). Cognitive science and folk psychology: The right frame of mind. Thousand Oaks: Sage Publications. |
| [37] | Hedden, T., & Zhang, J. (2002). What do you think I think you think?: Strategic reasoning in matrix games. Cognition, 85(1), 1-36. · doi:10.1016/S0010-0277(02)00054-9 |
| [38] | Isaac, AM; Szymanik, J.; Verbrugge, R.; Baltag, A. (ed.); Smets, S. (ed.), Logic and complexity in cognitive science, No. 5, 787-824 (2014), Berlin · Zbl 1319.91136 |
| [39] | Karp, R. M. (1972). Reducibility among combinatorial problems. In: Miller, R. E., Thatcher, J. W., Bohlinger, J. D. (Eds.), Complexity of computer computations: Proceedings of a symposium on the complexity of computer computations (pp. 85-103). Springer US, Boston, MA. https://doi.org/10.1007/978-1-4684-2001-2_9. · Zbl 1467.68065 |
| [40] | Kinderman, P., Dunbar, R., & Bentall, R. P. (1998). Theory-of-mind deficits and causal attributions. British Journal of Psychology, 89(2), 191-204. · doi:10.1111/j.2044-8295.1998.tb02680.x |
| [41] | Levesque, H. J. (1988). Logic and the complexity of reasoning. Journal of Philosophical Logic, 17(4), 355-389. · doi:10.1007/BF00297511 |
| [42] | Levin, L. A. (1973). Universal sequential search problems. Problems of Information Transmission, 9(3), 265-266. |
| [43] | Levinson, SC; Enfield, NJ (ed.); Levinson, SC (ed.), On the human ‘interaction engine’, 39-69 (2006), Oxford |
| [44] | Lyons, M., Caldwell, T., & Shultz, S. (2010). Mind-reading and manipulation—Is machiavellianism related to theory of mind? Journal of Evolutionary Psychology, 8(3), 261-274. · doi:10.1556/JEP.8.2010.3.7 |
| [45] | Marr, D. (1982). Vision: A computational investigation into the human representation and processing of visual information. San Francisco: WH Freeman. |
| [46] | Miller, S. A. (2009). Children’s understanding of second-order mental states. Psychological Bulletin, 135(5), 749-773. · doi:10.1037/a0016854 |
| [47] | Newell, A.; Simon, HA; Collins, AM (ed.); Smith, EE (ed.), GPS, a program that simulates human thought, 453-460 (1988), San Mateo, CA · doi:10.1016/B978-1-4832-1446-7.50040-6 |
| [48] | Nichols, S., & Stich, S. P. (2003). Mindreading: An integrated account of pretence, self-awareness, and understanding other minds. Oxford: Oxford University Press. · doi:10.1093/0198236107.001.0001 |
| [49] | Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford lecture series in mathematics and its applications. Oxford: Oxford University Press. · Zbl 1095.68038 · doi:10.1093/acprof:oso/9780198566076.001.0001 |
| [50] | Oaksford, M., & Chater, N. (1998). Rationality in an uncertain world: Essays on the cognitive science of human reasoning. Hove: Psychology Press. · doi:10.4324/9780203345955 |
| [51] | O’Grady, C., Kliesch, C., Smith, K., & Scott-Phillips, T. C. (2015). The ease and extent of recursive mindreading, across implicit and explicit tasks. Evolution and Human Behavior (in press). |
| [52] | Otworowska, M., Blokpoel, M., Sweers, M., Wareham, T., & van Rooij, I. (2017). Demons of ecological rationality. Cognitive Science. https://doi.org/10.1111/cogs.12530. |
| [53] | Premack, D., & Woodruff, G. (1978). Does the chimpanzee have a theory of mind? Behavioral and Brain Sciences, 1(04), 515-526. · doi:10.1017/S0140525X00076512 |
| [54] | Reiter, R. (1980). A logic for default reasoning. Artificial Intelligence, 13(1-2), 81-132. · Zbl 0435.68069 · doi:10.1016/0004-3702(80)90014-4 |
| [55] | Reyzin, L. (2006). 2-Player Tetris is PSPACE-hard. In Proceedings of the 16th fall workshop on computational and combinatorial geometry (FWCG 2006). |
| [56] | Ristad, E. S. (1993). The language complexity game. Cambridge, MA: MIT Press. |
| [57] | Slors, M. (2012). The model-model of the theory-theory. Inquiry, 55(5), 521-542. · doi:10.1080/0020174X.2012.716205 |
| [58] | Sperber, D., & Wilson, D. (1996). Relevance: Communication and Cognition. China: Wiley. |
| [59] | Stenning, K., & van Lambalgen, M. (2008). Human reasoning and cognitive science. Cambridge: MIT Press. |
| [60] | Stiller, J., & Dunbar, R. I. (2007). Perspective-taking and memory capacity predict social network size. Social Networks, 29(1), 93-104. · doi:10.1016/j.socnet.2006.04.001 |
| [61] | Stockmeyer, L. J., & Meyer, A. R. (1973) Word problems requiring exponential time (preliminary report). In: Proceedings of the 5th annual ACM symposium on the theory of computing (STOC 1973), ACM (pp 1-9). · Zbl 0359.68050 |
| [62] | Szymanik, J. (2016). Quantifiers and cognition. Logical and computational perspectives. Studies in linguistics and philosophy. Berlin: Springer. · Zbl 1432.03003 · doi:10.1007/978-3-319-28749-2 |
| [63] | Tsotsos, J. K. (1990). Analyzing vision at the complexity level. Behavioral and Brain Sciences, 13(3), 423-469. · doi:10.1017/S0140525X00079577 |
| [64] | van Benthem, J. (1977). Modal correspondence theory. Ph.D. thesis, Universiteit van Amsterdam. |
| [65] | van Benthem, J. (2011). Logical dynamics of information and interaction. Cambridge: Cambridge University Press. · Zbl 1251.03003 · doi:10.1017/CBO9780511974533 |
| [66] | van Ditmarsch, H., & Kooi, B. (2006). Semantic results for ontic and epistemic change. In Proceedings of the 7th conference on logic and the foundations of game and decision theory (LOFT 2006) (pp. 87-117). Amsterdam University Press. · Zbl 1261.03081 |
| [67] | van Ditmarsch, H., van der Hoek, W., & Kooi, B. P. (2008). Dynamic epistemic logic. Berlin: Springer. · Zbl 1156.03015 |
| [68] | van Eijck, J., & Schwarzentruber, F. (2014). Epistemic probability logic simplified. In Advances in modal logic (pp. 158-177). · Zbl 1385.03037 |
| [69] | van de Pol, I. (2015). How difficult is it to think that you think that i think that ...? A DEL-based Computational-level Model of Theory of Mind and its Complexity. Master’s thesis, University of Amsterdam, the Netherlands. |
| [70] | van de Pol, I., Szymanik, J., & van Rooij, I. (2015). Parameterized complexity results for a model of theory of mind based on dynamic epistemic logic. In: Ramanujam R (Ed.) Proceedings of the 15th conference on theoretical aspects of rationality and knowledge (TARK) (pp. 239-248). · Zbl 1483.68387 |
| [71] | van Rooij, I. (2003). Tractable cognition: Complexity theory in cognitive psychology. Ph.D. thesis, University of Victoria. |
| [72] | van Rooij, I. (2008). The tractable cognition thesis. Cognitive Science, 32(6), 939-984. · doi:10.1080/03640210801897856 |
| [73] | van Rooij, I. (2015). How the curse of intractability can be cognitive science’s blessing. In Proceedings of the 37th annual conference of the cognitive science society (pp. 2839-2840). |
| [74] | van Rooij, I., Kwisthout, J., Blokpoel, M., Szymanik, J., Wareham, T., & Toni, I. (2011). Intentional communication: Computationally easy or difficult? Frontiers in Human Neuroscience, 5(52), 1-18. |
| [75] | van Rooij, I., Stege, U., & Kadlec, H. (2005). Sources of complexity in subset choice. Journal of Mathematical Psychology, 49(2), 160-187. · Zbl 1115.91018 · doi:10.1016/j.jmp.2005.01.002 |
| [76] | van Rooij, I., & Wareham, T. (2008). Parameterized complexity in cognitive modeling: Foundations, applications and opportunities. The Computer Journal, 51(3), 385-404. · doi:10.1093/comjnl/bxm034 |
| [77] | van Rooij, I., & Wareham, T. (2012). Intractability and approximation of optimization theories of cognition. Journal of Mathematical Psychology, 56(4), 232-247. · Zbl 1282.91283 · doi:10.1016/j.jmp.2012.05.002 |
| [78] | Vardi, MY. (1995). On the complexity of bounded-variable queries (extended abstract). In Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems (PODS 1995) (pp. 266-276). ACM, New York, NY, USA. |
| [79] | Verbrugge, R. (2009). Logic and social cognition: the facts matter, and so do computational models. Journal of Philosophical Logic, 38(6), 649-680. · Zbl 1208.03022 · doi:10.1007/s10992-009-9115-9 |
| [80] | Wareham, H. T. (1999). Systematic parameterized complexity analysis in computational phonology. Ph.D. thesis, Department of Computer Science, University of Victoria, British Columbia, Canada. |
| [81] | Wellman, H. M., Cross, D., & Watson, J. (2001). Meta-analysis of theory-of-mind development: The truth about false belief. Child Development, 72(3), 655-684. · doi:10.1111/1467-8624.00304 |
| [82] | Wimmer, H., & Perner, J. (1983). Beliefs about beliefs: Representation and constraining function of wrong beliefs in young children’s understanding of deception. Cognition, 13(1), 103-128. · doi:10.1016/0010-0277(83)90004-5 |
| [83] | Zawidzki, T. W. (2013). Mindshaping: A New framework for understanding human social cognition. Cambridge: MIT Press. |
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.
