Convergence of Opinion Diffusion is PSPACE-Complete
Authors: Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini7103-7110
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the algorithmic properties of the fixed-point behaviour of such networks, showing that the problem of establishing whether individuals converge to stable opinions is PSPACE-complete.Our contribution is two-fold: firstly, we present some classes of networks which are guaranteed to converge, and secondly we show that the problem of establishing whether a network converges is PSPACE-complete even for the simplest of such protocols, closing a gap in the literature. |
| Researcher Affiliation | Academia | Dmitry Chistikov,1 Grzegorz Lisowski,1 Mike Paterson,1 Paolo Turrini1 1Department of Computer Science, University of Warwick, United Kingdom {d.chistikov, grzegorz.lisowski, m.s.paterson, p.turrini}@warwick.ac.uk |
| Pseudocode | No | The paper includes figures illustrating network gadgets (e.g., AND, NOT, NOP gates) and constructions, but it does not present any formal pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and does not mention or provide access to any open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments using datasets. Thus, it does not mention any publicly available or open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with data. Therefore, it does not specify any training/test/validation dataset splits. |
| Hardware Specification | No | The paper is purely theoretical and does not describe any experimental setup or the specific hardware used to run experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any software implementations or their dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity proofs rather than empirical experimentation. Therefore, it does not describe any experimental setup details, hyperparameters, or training settings. |