paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Orbit-finite linear programming

轨道有限线性规划
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 1/10 · 该论文属于逻辑、自动机与约束求解的理论工作,研究轨道有限线性规划的可判定性,与用户关注的 ML/Agent 静态分析、LLM 与静态分析/形式化验证交叉、浮点程序分析或贝叶斯程序分析均无直接关联。引用 5 inbox
Arka Ghosh, Piotr Hofman, Sławomir Lasota
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:证明轨道有限线性不等式组的实数可解性与优化可判定,并证明整数版本不可判定。

论文研究轨道有限线性规划:约束由轨道有限集合上的线性不等式系统给出,可视为普通线性规划在带原子置换对称性的无限集合上的推广。作者给出判定过程,用于检查该系统是否存在实数解,并计算线性目标函数在解集上的最小值或最大值。进一步证明,若只考虑整数解,相应的可解性与优化问题不可判定。由此得到主要结论:轨道有限线性规划在实数域可判定,而轨道有限整数线性规划不可判定。

问题
轨道有限线性不等式系统是否存在实数解,以及线性目标函数在该解集上的极值如何计算。
方法
通过给出判定过程,检查实数解并计算线性目标的最小/最大值。
评估
以可判定性/不可判定性证明作为理论评估,并对比整数解情形。
原文摘要(Abstract)

An infinite set is orbit-finite if, up to permutations of the underlying structure of atoms, it has only finitely many elements. We study a generalisation of linear programming where constraints are expressed by an orbit-finite system of linear inequalities. As our principal contribution we provide a decision procedure for checking if such a system has a real solution, and for computing the minimal/maximal value of a linear objective function over the solution set. We also show undecidability of these problems in case when only integer solutions are considered. Therefore orbit-finite linear programming is decidable, while orbit-finite integer linear programming is not.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@inproceedings{abs-2302-00802,
  title = {Orbit-finite linear programming},
  author = {Arka Ghosh and Piotr Hofman and Sławomir Lasota},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175799}
}