# P , NP, NP-Hard and NP-Complete: Complexity Classes Simplified

## P-Class

If any turing machine can solve a problem in polynomial time, then those problems fall under P-Class. As the name suggests, P stands for Polynomial since these problems only take polynomial amounts of time. For example, problems having the complexity of O(n), O(n²) belong to the P-Class problems. Since problems belonging to this set are solvable in polynomial amounts of time, these are also verifiable in polynomial time.

## NP-Class

Similarly, the problems belonging to NP-Class set are such problems that take non-polynomial (exponential) time in a deterministic turing machine. That is why they are known as NP-Class Problems. For example, problems having the complexity of O(2ⁿ), O(nⁿ) belong to the NP-Class problems. Also, to solve these problems, they do take polynomial time in a non-deterministic turing machine. Proofs of NP-Class problems are verifiable in polynomial time by any Turing machine.

## NP-Complete

The problems belonging to the NP-Complete class might feel confusing but, they would be clear once you see Venn’s Diagram at the end and read the following statements. Every element belonging to the NP-Complete set must satisfy the following given properties:

# Reduction

The following excerpt from Wikipedia can help you understand the reduction in the simplest way:

## NP-Hard

Problems in NP-Hard and NP-Complete are very similar, but problems belonging in the NP-Hard need not be present in the NP set. But, every problem residing in the NP-set must be reducible to ours to conclude that our problem belongs to the NP-Hard class. In short, a problem is in NP-Hard if it satisfies the second property of the NP-Complete. It doesn’t need to fulfill the first property of the NP-Complete class.