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.
Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic / van de Pol, Iris; van Rooij, Iris; Szymanik, Jakub. - In: JOURNAL OF LOGIC, LANGUAGE, AND INFORMATION. - ISSN 0925-8531. - 27:3(2018), pp. 255-294. [10.1007/s10849-018-9268-4]
Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic
Szymanik, Jakub
2018-01-01
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
s10849-018-9268-4.pdf
accesso aperto
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Creative commons
Dimensione
1.89 MB
Formato
Adobe PDF
|
1.89 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione