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

博文

A Generic Proof Of P != NP

已有 1993 次阅读 2017-2-7 14:41 |系统分类:观点评述

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.

 

 

 



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

上一篇:P and NP Problem Continued
下一篇:A Simple Partial Proof Of 3X + 1 Problem
收藏 IP: 203.219.90.*| 热度|

0

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

数据加载中...
扫一扫,分享此博文

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

GMT+8, 2024-5-1 03:27

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部