一句话：证明将 Presburger 算术扩展为代数无理数标量乘法后，判定复杂度显著升高，非二次情形甚至不可判定。
本文研究 Presburger 算术（PA）经代数无理数 α 的标量乘法扩展后得到的 α-PA。作者从判定复杂度入手，分析量词交替块数、变量与不等式数量对问题难度的影响。对于二次 α 且 r≥4，判定含 r 个交替量词块、至多 c r 个变量与不等式的 α-PA 语句至少需要高度为 r−3 的指数塔空间；进一步，判定某些 ∃^6∀^4∃^11 且不等式数受常数 k 限制的语句是 PSPACE-hard。对于非二次 α，仅四个交替量词块就足以导致 α-PA 语句不可判定。这表明该扩展远比 PA 困难。
We consider Presburger arithmetic (PA) extended by scalar multiplication by an algebraic irrational number $\alpha$, and call this extension $\alpha$-Presburger arithmetic ($\alpha$-PA). We show that the complexity of deciding sentences in $\alpha$-PA is substantially harder than in PA. Indeed, when $\alpha$ is quadratic and $r\geq 4$, deciding $\alpha$-PA sentences with $r$ alternating quantifier blocks and at most $c\ r$ variables and inequalities requires space at least $K 2^{\cdot^{\cdot^{\cdot^{2^{C\ell(S)}}}}}$ (tower of height $r-3$), where the constants $c, K, C>0$ only depend on $\alpha$, and $\ell(S)$ is the length of the given $\alpha$-PA sentence $S$. Furthermore deciding $\exists^{6}\forall^{4}\exists^{11}$ $\alpha$-PA sentences with at most $k$ inequalities is PSPACE-hard, where $k$ is another constant depending only on~$\alpha$. When $\alpha$ is non-quadratic, already four alternating quantifier blocks suffice for undecidability of $\alpha$-PA sentences.
@article{paperbot1302,
title = {Presburger Arithmetic with algebraic scalar multiplications},
author = {Philipp Hieronymi and Danny Nguyen and Igor Pak},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 3},
year = {2021},
doi = {10.46298/lmcs-17(3:4)2021}
}