|
A Generic Proof Of P != NP Suppose a decision problem f(n) is Boolean (NP), its time complexity is n ^ c, where c <= a contant. When n increases, the possible data instances will increase and total number of possible instances will be 2 ^ n. In order to solve the problem using DTM, the time complexity must satisfy n ^ c >= 2 ^ n So c <= consant is not possible! A Generic Proof Of P != NP is true.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-19 21:56
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社