How Hard to Tell? Complexity of Belief Manipulation Through Propositional Announcements
Authors: Thomas Eiter, Aaron Hunter, Francois Schwarzentruber
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper studies the problem of the existence of such an announcement in the context of model-preference definable revision operators. First, we provide two characterisation theorems for the existence of announcements: one in the general case, the other for total preorders. Second, we exploit the characterisation theorems to provide upper complexity bounds. Finally, we also provide matching optimal lower bounds for the Dalal and Ginsberg operators. |
| Researcher Affiliation | Academia | Thomas Eiter1 , Aaron Hunter2 , Franc ois Schwarzentruber3 1Vienna University of Technology (TU Wien) 2British Columbia Institute of Technology 3 Ecole Normale Sup erieure de Rennes eiter@kr.tuwien.ac.at, aaron hunter@bcit.ca, francois.schwarzentruber@ens-rennes.fr |
| Pseudocode | Yes | Consider the following non-deterministic algorithm: for i := 1 to n do choose µi in mod(ψi) for i, j {1, . . . , n} do if µi |= ψj then Check that µj Ki µi µi Ki µj |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper focusing on computational complexity, not empirical studies involving datasets for training. |
| Dataset Splits | No | This is a theoretical paper focusing on computational complexity, not empirical studies involving dataset splits for validation. |
| Hardware Specification | No | The paper does not provide specific hardware details for running experiments, as it is a theoretical paper. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper does not provide specific experimental setup details such as hyperparameter values or training configurations, as it is a theoretical paper. |