Theory of Computation20795 marksComplexity Classes
Explain about the complexity classes p, NP and NP-Complete.
Explain about the complexity classes p, NP and NP-Complete. [5]
P (Polynomial Time) is the class of decision problems that can be solved by a deterministic Turing machine in polynomial time with respect to the input size n. - A problem belongs to P if there exists an algorithm that solves it in O(n^k) time for some constant k. - These are considered efficient...