cs.AI updates on arXiv.org 10月13日 12:13
信息论框架揭示P≠NP
index_new5.html
../../../zaker_core/zaker_tpl_static/wap/tpl_guoji1.html

 

该研究提出了一种结合信息论、程序合成和对称性与稀疏性的框架,用于分析计算复杂性。研究人员通过将短程序转化为局部性,并利用掩码随机唯一SAT的对称性和稀疏性,推导出分布式的下界。这些下界与NP=P假设下的自约简上界相矛盾。具体而言,通过引入一个“切换-弱化”的范式,证明了对于多项式时间解码器,短包装器可以使其在大部分独立块上具有局部性。结合符号不变中立性引理和对数半径内的模板稀疏化定理,研究表明任何局部规则的出现概率都很低。最终,通过压缩成功率,推导出元组复杂度至少是线性增长的,这与NP=P假设下的常数复杂度相矛盾,从而证明了NP≠P。此方法是非相对化且非自然化的。

💡 **信息论框架与局部性转化**:研究提出了一种新颖的信息论框架,能够将短程序转化为局部性,并应用于多个独立的数据块。这种转化使得对程序的分析能够聚焦于局部信息,为后续的复杂性证明奠定了基础。

⚖️ **对称性与稀疏性在复杂性证明中的应用**:通过结合掩码随机唯一SAT的对称性和稀疏性,研究人员推导出了分布式的下界。这表明在特定条件下,信息的结构化特性可以用来限制计算的复杂性,从而挑战了NP=P的假设。

📉 **分布下界与自约简上界的矛盾**:研究的核心在于,通过上述框架和技术,推导出的分布式下界与NP=P假设下的自约简上界存在矛盾。这种矛盾直接指向了P≠NP的结论,即NP类问题无法在多项式时间内解决。

🚀 **非相对化、非自然化的证明方法**:该研究的证明方法具有非相对化和非自然化的特点,意味着其结论并非依赖于特定的Oracle或计算模型,而是基于更普适的计算原理。这种证明方式的突破性在于其通用性和鲁棒性。

arXiv:2510.08814v1 Announce Type: cross Abstract: We give a compositional, information-theoretic framework that turns short programs into locality on many independent blocks, and combine it with symmetry and sparsity of masked random Unique-SAT to obtain distributional lower bounds that contradict the self-reduction upper bound under $\mathsf{P}=\mathsf{NP}$. We work in the weakness quantale $wQ=K{\mathrm{poly}}(\cdot\mid\cdot)$. For an efficiently samplable ensemble $D_m$ made by masking random $3$-CNFs with fresh $S_m\ltimes(\mathbb{Z}_2)^m$ symmetries and a small-seed Valiant--Vazirani isolation layer, we prove a Switching-by-Weakness normal form: for any polytime decoder $P$ of description length $\le \delta t$ (with $t=\Theta(m)$ blocks), a short wrapper $W$ makes $(P\circ W)$ per-bit local on a $\gamma$-fraction of blocks. Two ingredients then force near-randomness on $\Omega(t)$ blocks for every short decoder: (a) a sign-invariant neutrality lemma giving $\Pr[Xi=1\mid \mathcal{I}]=1/2$ for any sign-invariant view $\mathcal{I}$; and (b) a template sparsification theorem at logarithmic radius showing that any fixed local rule appears with probability $m^{-\Omega(1)}$. Combined with single-block bounds for tiny $\mathrm{ACC}^0$/streaming decoders, this yields a success bound $2^{-\Omega(t)}$ and, by Compression-from-Success, $K{\mathrm{poly}}\big((X_1,\ldots,X_t)\mid(\Phi_1,\ldots,\Phit)\big)\ge \eta t$. If $\mathsf{P}=\mathsf{NP}$, a uniform constant-length program maps any on-promise instance to its unique witness in polytime (bit fixing via a $\mathrm{USAT}$ decider), so $K{\mathrm{poly}}(X\mid\Phi)\le O(1)$ and the tuple complexity is $O(1)$, contradicting the linear bound. The proof is non-relativizing and non-natural; symmetry, sparsification, and switching yield a quantale upper-lower clash, hence $\mathsf{P}\ne\mathsf{NP}$.

Fish AI Reader

Fish AI Reader

AI辅助创作,多种专业模板,深度分析,高质量内容生成。从观点提取到深度思考,FishAI为您提供全方位的创作支持。新版本引入自定义参数,让您的创作更加个性化和精准。

FishAI

FishAI

鱼阅,AI 时代的下一个智能信息助手,助你摆脱信息焦虑

联系邮箱 441953276@qq.com

相关标签

P≠NP 计算复杂性 信息论 分布式下界 对称性 稀疏性 非相对化证明 P vs NP Computational Complexity Information Theory Distributional Lower Bounds Symmetry Sparsity Non-Relativizing Proof
相关文章