计算机科学 > 计算机科学中的逻辑
[提交于 2025年9月26日
]
标题: 结构分离与P vs. NP问题中的语义不相容性:用构造定义功能进行计算复杂性分析
标题: Structural Separation and Semantic Incompatibility in the P vs. NP Problem: Computational Complexity Analysis with Construction Defining Functionality
摘要: 布尔可满足性问题(SAT)在计算复杂性理论中占据中心地位,作为第一个被证明是NP完全的问题。 由于这一作用,SAT经常被用作多项式时间归约的基准:如果一个问题可以归约到SAT,那么它至少和SAT一样难,因此被认为是NP完全的。 然而,CDF框架提供了一种对这种传统观点的结构反转。 不仅仅是将SAT视为NP完全性的代表,我们研究SAT本身的句法结构——尤其是其3SAT形式——是否是NP问题中观察到的语义爆炸和计算难解性的来源。 换句话说,SAT不仅是NP完全性的标尺,也可能是导致NP型复杂性的结构原型。 这种重新表述表明,P与NP问题不仅根植于计算资源的限制,还根植于问题句法的生成原则,其中3SAT捕捉到了定义易处理和难处理问题之间边界的递归和非局部构造。
文献和引用工具
与本文相关的代码,数据和媒体
alphaXiv (什么是 alphaXiv?)
CatalyzeX 代码查找器 (什么是 CatalyzeX?)
DagsHub (什么是 DagsHub?)
Gotit.pub (什么是 GotitPub?)
Hugging Face (什么是 Huggingface?)
带有代码的论文 (什么是带有代码的论文?)
ScienceCast (什么是 ScienceCast?)
演示
推荐器和搜索工具
arXivLabs:与社区合作伙伴的实验项目
arXivLabs 是一个框架,允许合作伙伴直接在我们的网站上开发和分享新的 arXiv 特性。
与 arXivLabs 合作的个人和组织都接受了我们的价值观,即开放、社区、卓越和用户数据隐私。arXiv 承诺这些价值观,并且只与遵守这些价值观的合作伙伴合作。
有一个为 arXiv 社区增加价值的项目想法吗? 了解更多关于 arXivLabs 的信息.