paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Prime Factorization in Models of PV$_1$

PV₁ 模型中的素因子分解
LMCS vol.Volume 22, Issue 22026匹配度 1/10 · 论文属于有界算术与证明复杂性,研究 PV1 在密码学假设下无法证明素数因子存在,并构造非标准模型;这与用户关注静态分析、LLM/Agent 程序分析、浮点或贝叶斯程序分析均无直接关联。引用 1 inbox
Ondřej Ježil
crossref: 2026-09-10

AI 速览

一句话:在特定密码学困难性假设下,PV₁ 即使加入 BB(Σ^b_0) 也不能证明每个数有素因子,并由此得到非标准模型。

本文研究有界算术理论 PV₁ 能否证明每个自然数都有素因子。作者假设不存在多项式大小的布尔电路族能分解所有两个 n 比特素数乘积中的常数比例,在此假设下证明:即使将 PV₁ 加强为加入 sharply bounded choice scheme BB(Σ^b_0) 的理论,仍不能证明“每个数都有某个素因子”。随后利用完备性定理,得到该假设下存在 PV₁ 的模型 M,其中含有一个非标准数 m,而 m 没有任何素因子分解。该结果将分解困难性假设与有界算术的证明能力及非标准模型的存在性联系起来。

问题
PV₁ 及其加 BB(Σ^b_0) 的扩展能否证明每个自然数都有素因子?
方法
在“无多项式大小电路能分解常数比例的两个 n 比特素数乘积”的假设下,通过有界算术的不可证明性论证与完备性定理构造模型。
评估
以理论证明和复杂度假设下的不可证明性结果进行评估,未涉及实现或实验;结论是相应理论不能证明该命题并存在非标准反例模型。
原文摘要(Abstract)

Assuming that no family of polynomial-size Boolean circuits can factorize a constant fraction of all products of two $n$-bit primes, we show that the bounded arithmetic theory $\text{PV}_1$, even when augmented by the sharply bounded choice scheme $BB(Σ^b_0)$, cannot prove that every number has some prime divisor. By the completeness theorem, it follows that under this assumption there is a model $M$ of $\text{PV}_1$ that contains a nonstandard number $m$ which has no prime factorization.

链接与引用

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

BibTeX
@article{abs-2505-14516,
  title = {Prime Factorization in Models of PV$_1$},
  author = {Ondřej Ježil},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 22, Issue 2},
  year = {2026},
  doi = {10.46298/lmcs-22(2:1)2026}
}