CS 502
Topic:
“NP complete problems are solvable /decidable problems.” Support or contradict the statement with solid
arguments with respect to time constraints. Only two to three sentences are
required to give the complete idea.
Comments:
Apparently
some problems are “harder” in a relative sense than the other problems within
the NP-class of problems. If you can write polynomial algorithm for any one of
this group of apparently hard problems, then it can be shown that every
NP-class problem will have a polynomial algorithm for each. This group of
problems is called NP-complete
problems. if there is no HC in a
given input graph then HC-problem may not be solved in polynomial time even
with non-deterministic algorithms. Some problems are even unsolvable/
un-decidable algorithmically, for which we cannot write a computer program for
them.
No comments:
Post a Comment
“You can't change the past, but you can ruin the present by worrying about the future”