For each of the following give a definition 1 The complexity

For each of the following give a definition:

1. The complexity class P.
2. The complexity class NP.
3. The complexity class L.

Solution

Definition of :

P : It is defined as the class of polynomially solvable problems, P which contains all sets where membership may be decided by an algorithm whose running time is bounded by a polynomial.

NP :It is defined as the class of nondeterministic polynomially acceptable problems, NP, which contains all sets where membership can be verified in polynomial time.