Theory of Computation20815 marksComplexity Classes
Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA, and ε-NFA.
Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA, and ε-NFA. [5]
--- Basis Class P Class NP --------- Full Form Polynomial Time Non-deterministic Polynomial Time Definition Set of decision problems solvable by a deterministic Turing machine in polynomial time O(n^k) Set of decision problems solvable by a non-deterministic Turing machine in polynomial time Trac...