|
By one definition,
P is the problem sovable in polynomial time using DTM,
NP is the problem sovable in polynomial time using NDTM.
Basically, NDTM is a multiple copies of DTM because it can
have mutiple branch computations.
From this definition, it is very clear that P != NP
because it's very easy to design a problem to satisfy it.
Time complexity has nothing to do with the machine structures
whether you use 1-bit or 1000-bit, or simple machine or super
machine, the results are the same.
Time complexity only relate to possible problem data instances.
So many or even 'most' Boolean problems are or should be
at least exponential.
As for the Hamiltonian problem, you can construct
a search tree, where the time complexity of each branch
tree is much larger than exponential, and this can be
easily proved. This is not only theory, practical implementation
will surely get this result if they are correctly implemented and
correct worst-case instances are tested.
Posa's algorithm is just another representation of search tree
and is not complete. Its implementation has many problems.
Some people say they tested an input size of n = 10000 within
10 minutes. You are joking!
With a size of this, if you started testing before the formation of
our universe with the most powerful computer, you are now just
finished the test input.
When will you finish the test?
It may well be that after the vanishing of our universe, you are still
at the beginning of your test!
Why, it will cost 1000000000000......full of 00000000000 years to
finish.
This is true!
This blog is just an exercise! Take it for a ride.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-20 02:01
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社