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 |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=94254804&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 94254804 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00397857 4LI jtl: Synthese issn: 00397857 maglogo: N pubinfo: dt: Feb2014 vid: 191 iid: 3 pid: 237 pub: Springer Nature artinfo: ui: 94254804 10.1007/s11229-012-0215-7 ppf: 371 ppct: 38 formats: fmt: @attributes: type: P size: 411KB tig: atl: Exploring the tractability border in epistemic tasks. aug: au: Dégremont, Cédric Kurzen, Lena Szymanik, Jakub affil: Institute of Artificial Intelligence, University of Groningen, Groningen The Netherlands Institute for Logic, Language and Computation, University of Amsterdam, Amsterdam The Netherlands su: Epistemic logic Computational complexity Decision making Comparative studies Multiagent systems sug: subj: Epistemic logic Computational complexity Decision making Comparative studies Multiagent systems keyword: Epistemic reasoning Multi-agent systems ab: 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. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y custom: Synthese is a copyright of Springer, 2014. All Rights Reserved. item: Synthese holder: Springer Nature dt: @attributes: year: 2014 holdings: @attributes: islocal: N |
|---|