five

Invariance of Initial Conditions in P and NP and Structural Incompatibility Between Problems with Hypothetical "Additional Hidden Properties" Allowing Partial Solutions to Each

收藏
Mendeley Data2026-04-18 收录
下载链接:
https://data.mendeley.com/datasets/bgxfpx8238
下载链接
链接失效反馈
官方服务:
资源简介:
The question of the relationship between the classes P and NP is one of the central problems in modern complexity theory. The usual line of attack on the problem seeks either to find a polynomial-time algorithm for solving an NP-complete problem or to prove its nonexistence. In the present work, we will consider an alternative approach: we will explore the possibility of resolving the P versus NP problem by establishing a contradiction between the necessary conditions for efficiently solving different NP-complete problems. That is, if a solution is found for one problem through some new hidden property, this property would be in conflict with an analogous property needed to solve another problem. The focus will be on the role of hidden properties in the input of the problems and their impact on the possibility of universal mutual reduction between them.

P类与NP类之间的关系问题,是现代复杂度理论的核心问题之一。针对该问题的常规研究路径,要么旨在为NP完全(NP-complete)问题寻得多项式时间求解算法,要么证明此类算法不存在。 本研究将探讨一条替代路径:通过构建不同NP完全问题在高效求解所需必要条件间的矛盾,来尝试解决P与NP的关系问题。换言之,若通过某一全新的隐藏性质为某一NP完全问题找到求解方案,则该性质将与求解另一同类问题所需的类似性质产生冲突。 本研究的重点将聚焦于问题输入中隐藏性质的作用,以及这些性质对两类问题间通用互归约可能性的影响。
创建时间:
2025-04-29
二维码
社区交流群
二维码
科研交流群
商业服务