|
Time Complexity Is Purely Theoretical,
Yes, this is true, no matter what computing structures are used,
time complexity will not change.
You can use DTM or other computing structures for this purpose.
This is for the preservation of the exact, theoretical meaning of its
definition.
Any complexity difference between practical computing structures is
a costant and by convention, constants are omitted for complexity notation.
For the proof of P != NP, it has nothing to do with CH, they are two
different problems, the proof or disproof of one do not mean another.
Also note that NPI is not only unnecessary but also non-existent
due to NP's great different coverage, and there is a clear distiction
between quantity and quality.
This imply many consequences.
First of all, it is a very important tool for IT professionals, especially
for software engineers for the estimation or development of software
products of small input size n.
Although T(n) will not change categories, it will give execution time estimation
for different problem sizes n and different machine structures as references.
Most important is its indispensible methods to use knowledge to derive the results.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-20 02:00
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社