Design and Analysis of Algorithms20825 marksComplexity Classes
Define class P and NP problem. Why do we need approximation algorithms? Justify.
Define class P and NP problem. Why do we need approximation algorithms? Justify. [5]
Class P (Polynomial time) is the class of decision problems that can be solved by a deterministic algorithm in polynomial time, i.e., in O(n^k) time for some constant k, where n is the size of the input. - These are considered "efficiently solvable" problems. - Examples: Sorting, Shortest path (D...