Parameterized Complexity Results for a Model of Theory of Mind Based on Dynamic Epistemic Logic
In this paper we introduce a computational-level model of theory of mind (ToM) based on dynamic epistemic logic (DEL), and we analyze its computational complexity. The model is a special case of DEL model checking. We provide a parameterized complexity analysis, considering several aspects of DEL (e.g., number of agents, size of preconditions, etc.) as parameters. We show that model checking for DEL is PSPACE-hard, also when restricted to single-pointed models and S5 relations, thereby solving an open problem in the literature. Our approach is aimed at formalizing current intractability claims in the cognitive science literature regarding computational models of ToM.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
From Theory of Mind to Theory of Environment: Counterfactual Simulation of Latent Environmental Dynamics
The vertebrate motor system employs dimensionality-reducing strategies to limit the complexity of movement coordination, for efficient motor control. But when environments are dense with hidden action-outcome contingenci…
A Parameterized Theory of PAC Learning
Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexit…
PAC learningA Parameterized Complexity View on Description Logic Reasoning
Description logics are knowledge representation languages that have been designed to strike a balance between expressivity and computational tractability. Many different description logics have been developed, and numero…
Parameterized Complexity Analysis of Randomized Search Heuristics
This chapter compiles a number of results that apply the theory of parameterized algorithmics to the running-time analysis of randomized search heuristics such as evolutionary algorithms. The parameterized approach artic…
Combinatorial OptimizationEvolutionary AlgorithmsTowards A Theory-Of-Mind-Inspired Generic Decision-Making Framework
Simulation is widely used to make model-based predictions, but few approaches have attempted this technique in dynamic physical environments of medium to high complexity or in general contexts. After an introduction to t…
Decision Making