遇见数据集

P $\neq$ NP: A Proof via Finite Information Capacity of Physical Computation

收藏
Zenodo2026-05-09 更新2026-05-26 收录
官方服务:

资源简介:

We prove that P $\neq$ NP. Any physical computer operates within the observable universe, which has a finite information capacity bounded by the holographic principle: $I_{\text{max}} \sim 10^{122}$ bits. A polynomial-time algorithm for an NP-complete problem would need to distinguish exponentially many states, which exceeds the physical bound for sufficiently large input size. We formalize this using the circuit model of computation and the Margolus-Levitin bound on computational speed. For 3-SAT with $n > I_{\text{max}}$ variables, no physical computer can correctly decide all inputs in polynomial time. Therefore 3-SAT $\notin$ P, and since 3-SAT is NP-complete, P $\neq$ NP. This constitutes a proof of the P versus NP problem, one of the seven Clay Millennium Prize problems.

提供机构:
Zenodo
创建时间:
2026-05-09
二维码
社区交流群
二维码
科研交流群
商业服务