|
P (DTM) 运行在整数环上,NP (NDTM) 运行在Q[i]={a+bi}域上, Q 为有理数集。
因此,P的派生矩阵为线性相关,NP的派生矩阵可以为线性无关。
任意的p ∈ P,LinearDep(p)= true;
存在 np ∈ NP, LinearDep(np) = false;
因此,P ≠ NP
https://doi.org/10.48550/arXiv.2303.03958 |
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2023-9-27 02:52
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社