Repository | Journal | Volume | Articles
(2014) Synthese 191 (3).
Exploring the tractability border in epistemic tasks
Cédric Dégremont, Lena Kurzen, Jakub Szymanik
pp. 371-408
We analyse the computational complexity of comparing informational structures. Intuitively, we study the complexity of deciding queries such as the following: Is Alice’s epistemic information strictly coarser than Bob’s? Do Alice and Bob have the same knowledge about each other’s knowledge? Is it possible to manipulate Alice in a way that she will have the same beliefs as Bob? The results show that these problems lie on both sides of the border between tractability (P) and intractability (NP-hard). In particular, we investigate the impact of assuming information structures to be partition-based (rather than arbitrary relational structures) on the complexity of various problems. We focus on the tractability of concrete epistemic tasks and not on epistemic logics describing them.
Publication details
DOI: 10.1007/s11229-012-0215-7
Full citation:
Dégremont, C. , Kurzen, L. , Szymanik, J. (2014). Exploring the tractability border in epistemic tasks. Synthese 191 (3), pp. 371-408.
This document is unfortunately not available for download at the moment.