|
Although satisfiability problem can has any format, in order to prove P = NP, it must take
the 'most difficult' and 'most efficient' form for the satisfaction of NP completeness.
For this purpose, any implementation of satisfiability problem require at least
2 ^ n
time complexity, this is also the possible input data items.
Therefore, N = NP will ever be possible, and P != NP is true.
This is a theorem now.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-4-27 13:32
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社