跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2502.02220 · v5

On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number

首次提交 2025-02-04 18:59
版本更新 2026-11-14 00:35
雷达观测 2026-11-16 11:41
arXiv ↗PDF ↗

摘要

This paper investigates ∃R(rZ)\exists\mathbb{R}(r^{\mathbb{Z}}), that is the extension of the existential theory of the reals by an additional unary predicate rZr^{\mathbb{Z}} for the integer powers of a fixed computable real number r>0r > 0. If all we have access to is a Turing machine computing rr, it is not possible to decide whether an input formula from this theory satisfiable. However, we show an algorithm to decide this problem when: 1. rr is known to be transcendental, or 2. rr is a root of some given integer polynomial (that is, rr is algebraic). In other words, knowing the algebraicity of rr suffices to circumvent undecidability. Furthermore, we establish complexity results under the proviso that rr enjoys what we call a polynomial root barrier. Using this notion, we show that the satisfiability problem of ∃R(rZ)\exists\mathbb{R}(r^{\mathbb{Z}}) is 1. in NEXPTIME if rr is a natural number, 2. in EXPSPACE if rr is an algebraic number, and 3. in 3EXP if rr belongs to a family of transcendental numbers including $π$ and Euler's ee. As a by-product of our results, we are able to remove the appeal to Schanuel's conjecture from the proof of decidability of the entropic risk threshold problem for stochastic games with rational probabilities, rewards and threshold [Baier et al., MFCS'23]: when the base of the entropic risk is Euler's ee and the aversion factor is a fixed algebraic number, the problem is in EXP.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v5,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v5 · 2026-11-14 00:35 · 最新观测版本

On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number

This paper investigates ∃R(rZ)\exists\mathbb{R}(r^{\mathbb{Z}}), that is the extension of the existential theory of the reals by an additional unary predicate rZr^{\mathbb{Z}} for the integer powers of a fixed computable real number r>0r > 0. If all we have access to is a Turing machine computing rr, it is not possible to decide whether an input formula from this theory satisfiable. However, we show an algorithm to decide this problem when: 1. rr is known to be transcendental, or 2. rr is a root of some given integer polynomial (that is, rr is algebraic). In other words, knowing the algebraicity of rr suffices to circumvent undecidability. Furthermore, we establish complexity results under the proviso that rr enjoys what we call a polynomial root barrier. Using this notion, we show that the satisfiability problem of ∃R(rZ)\exists\mathbb{R}(r^{\mathbb{Z}}) is 1. in NEXPTIME if rr is a natural number, 2. in EXPSPACE if rr is an algebraic number, and 3. in 3EXP if rr belongs to a family of transcendental numbers including $π$ and Euler's ee. As a by-product of our results, we are able to remove the appeal to Schanuel's conjecture from the proof of decidability of the entropic risk threshold problem for stochastic games with rational probabilities, rewards and threshold [Baier et al., MFCS'23]: when the base of the entropic risk is Euler's ee and the aversion factor is a fixed algebraic number, the problem is in EXP.

查看此版本解读 →查看此版本原文 ↗