Exploring the tractability border in epistemic tasks.
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 po...
| Publicado en: | Synthese Vol. 191; no. 3; pp. 371 - 409 |
|---|---|
| Autores principales: | , , |
| Formato: | Artículo |
| Publicado: |
Springer Nature
Feb2014
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| Sumario: | 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. |
|---|