DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.26

Coordinating "7 Billion Humans" Is Hard

Authors: Alessandro Panconesi, Pietro Maria Posta, and Mirko Giacchini

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

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.

Cite as

Alessandro Panconesi, Pietro Maria Posta, and Mirko Giacchini. Coordinating "7 Billion Humans" Is Hard. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{panconesi_et_al:LIPIcs.FUN.2024.26,
  author =	{Panconesi, Alessandro and Posta, Pietro Maria and Giacchini, Mirko},
  title =	{{Coordinating "7 Billion Humans" Is Hard}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.26},
  URN =		{urn:nbn:de:0030-drops-199342},
  doi =		{10.4230/LIPIcs.FUN.2024.26},
  annote =	{Keywords: video games, computational complexity, NP, PSPACE}
}

Search Results

Documents authored by Giacchini, Mirko

Coordinating "7 Billion Humans" Is Hard

Abstract

Cite as