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

博文

Some Summary Of Time Complexity

已有 1660 次阅读 2016-12-20 01:41 |系统分类:观点评述

We have known the basic time complexity classes or types of constant, polynomial, 

and exponential.

These classes or types are pure or simple.

In order to solve many problems for practical applications, people defined

some other classes or types: NP, NP complete, NP hard, etc.

These classes or types are problem-specific complex classes,

that can be defined in many ways in respect to time and space.

As a class or type, each of them imply a group or a set.

A simple problem in P is also in NP and in NP hard,

A simple problem in NP is also in NP hard but may or may not be in P.

A simple problem in NP hard may or may not be in P or NP.

A simple NP hard problem is not necessarily harder than 

a simple P or NP problem.

NP complete or hard problems do not exist.

So Sat. Ham. DTSP. and so on so forth are not NP complete.

Reductions or transformations in thses types and others are 

not required or do not follow the usual rules.

TSP. is not NP 'complete' but 'hard' as defined.

The time order for these problems is roughly:

TSP. > DTSP. > Ham. > Sat.

For solving the time complexity problem of one particular class or type,

a static- to-dynamic view should be used.

A effective way to test such an implementation is first to test it theoretically.

 

Please cite.

 

 

 



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

上一篇:P AND NP RELATED TIME COMPLEXITY
下一篇:Boatman's Conjecture
收藏 IP: 203.219.90.*| 热度|

0

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

数据加载中...

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

GMT+8, 2024-4-27 03:26

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部