Coordinating "7 Billion Humans" is hard
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916318212521984 |
|---|---|
| author | Panconesi, Alessandro Posta, Pietro Maria Giacchini, Mirko |
| author_facet | Panconesi, Alessandro Posta, Pietro Maria Giacchini, Mirko |
| contents | In the video game "7 Billion Humans", the player is requested to direct a group of workers to various destinations by writing a program that is executed simultaneously on each worker. While the game is quite rich and, indeed, it is considered one of the best games for beginners to learn the basics of programming, we show that even extremely simple versions are already NP-Hard or PSPACE-Hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_07246 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Coordinating "7 Billion Humans" is hard Panconesi, Alessandro Posta, Pietro Maria Giacchini, Mirko Computational Complexity In the video game "7 Billion Humans", the player is requested to direct a group of workers to various destinations by writing a program that is executed simultaneously on each worker. While the game is quite rich and, indeed, it is considered one of the best games for beginners to learn the basics of programming, we show that even extremely simple versions are already NP-Hard or PSPACE-Hard. |
| title | Coordinating "7 Billion Humans" is hard |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2407.07246 |