We introduce the complexity class Quantified Reals ($\text{Q}\mathbb{R}$). Let FOTR be the set of true sentences in the first-order theory of the reals. A language $L$ is in $\text{Q}\mathbb{R}$, if there is a polynomial time reduction from $L$ to FOTR. This seems the first time this complexity class is studied. We show that $\text{Q}\mathbb{R}$ can also be defined using real Turing machines. It is known that deciding FOTR requires at least exponential time unconditionally [Berman, 1980]. We focus on devil's games with two defining properties: (1) Players (human and devil) alternate turns and (2) each turn has a continuum of options. First, we show that FOTRINV is $\text{Q}\mathbb{R}$-complete. FOTRINV has only inversion and addition constraints and all variables are in a compact interval. FOTRINV is a stepping stone for further reductions. Second, we show that the Packing Game is $\text{Q}\mathbb{R}$-complete. In the Packing Game we are given a container and two sets of pieces. One set of pieces for the human and one set for the devil. The human and the devil alternate by placing a piece into the container. Both rotations and translations are allowed. The first player that cannot place a piece loses. Third, we show that the Planar Extension Game is $\text{Q}\mathbb{R}$-complete. We are given a partially drawn plane graph and the human and the devil alternate by placing vertices and the corresponding edges in a straight-line manner. The vertices and edges to be placed are prescribed before hand. The first player that cannot place a vertex loses. Finally, we show that the Order Type Game is $\text{Q}\mathbb{R}$-complete. We are given an order-type together with a linear order. The human and the devil alternate in placing a point in the Euclidean plane following the linear order. The first player that cannot place a point correctly loses.

翻译：本文引入复杂度类量化实数（$\text{Q}\mathbb{R}$）。令FOTR为实数一阶理论中的真语句集合。若语言$L$可通过多项式时间归约至FOTR，则$L$属于$\text{Q}\mathbb{R}$。这似乎是该复杂度类首次被系统研究。我们证明$\text{Q}\mathbb{R}$也可通过实数图灵机定义。已知无条件判定FOTR至少需要指数时间[Berman, 1980]。我们聚焦于具有两个定义特性的魔鬼博弈：（1）玩家（人类与魔鬼）交替行动；（2）每步行动具有连续统量级的选项。首先，我们证明FOTRINV是$\text{Q}\mathbb{R}$-完备的。FOTRINV仅包含取逆与加法约束，且所有变量均处于紧致区间内。FOTRINV是后续归约的关键桥梁。其次，我们证明装箱博弈是$\text{Q}\mathbb{R}$-完备的。在该博弈中，给定一个容器及两组拼块，分别由人类与魔鬼持有。双方通过旋转与平移操作交替将拼块放入容器，首个无法放置拼块的玩家判负。第三，我们证明平面扩展博弈是$\text{Q}\mathbb{R}$-完备的。给定部分绘制的平面图，双方按预定顺序以直线方式交替放置顶点及对应边，首个无法放置顶点的玩家判负。最后，我们证明序型博弈是$\text{Q}\mathbb{R}$-完备的。给定序型与线性序，双方在欧几里得平面上按线性序交替放置点，首个无法正确放置点的玩家判负。