NP = P?

Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.
P denotes set of problems which can be solved in polynomial time i.e. having solution times proportional to O(n raise to k), k is any constant. Whereas, NP is class of problems whose solution can be verified in polynomial time and its solution times for some inputs might go near exponential times or so...
The question “Does NP equal P?” means “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?”
Click here to read more...

P, NP, and NP-Completeness: The Basics of Computational Complexity

No comments:

Post a Comment