Overview of the Universe分享 http://blog.sciencenet.cn/u/xshi Essentials of Science and Technology

博文

Satisfiability Problem and NP Completenss

已有 1944 次阅读 2016-12-5 19:00 |系统分类:观点评述

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.

 

 

 



https://wap.sciencenet.cn/blog-530158-1018872.html

上一篇:Goldbach Conjecture
下一篇:Hamiltonian Problem
收藏 IP: 203.219.90.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-4-27 13:32

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部