Devil’s Games and Q ​ ℝ \textsc{Q}\mathbb{R} Continuous Games complete for the First-Order Theory of the Reals.

Lucas Meijer, Arnaud de Mesmay, Tillmann Miltzow, Marcus Schaefer, Jack Stade · 2025

Read Devil’s Games and Q ​ ℝ \textsc{Q}\mathbb{R} Continuous Games complete for the First-Order Theory of the Reals. by Lucas Meijer, Arnaud de Mesmay, Tillmann Miltzow, Marcus Schaefer, Jack Stade (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-02779.txt.

Description

Lucas Meijer and four co-authors define a new complexity class for problems about real numbers. Complexity classes sort problems by the resources needed to solve them. Their class, Quantified Reals, collects languages reducible in polynomial time to true sentences of the first order theory of the reals.

Alongside it they study continuous games, nicknamed Devil's games in the title. The class proves complete for that theory, giving it a firm anchor. New landmarks in complexity help researchers place fresh problems quickly and compare the hardness of games, geometry, and logic. New rungs on the scale of hard tasks help all who sort tasks for a life, from games to proofs of law.

Catalog record

CREATORLucas Meijer, Arnaud de Mesmay, Tillmann Miltzow, Marcus Schaefer, Jack Stade
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE190 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-02779

Browse the full library · About the Tower of Babel