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

Can a computer solve all computational problems? Currently, the answer is no, but for solvable problems, how much time would it take? This question has led us to discuss this topic in detail.

A Zoomed-In Microprocessor is present in this image so that we see its key components inside it. The microprocessor is depicting the processing power to solve computational problems.
Photo by Ryan on Unsplash

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.

Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete, and in general, not every problem in P or NP is NP-complete).
Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete, and in general, not every problem in P or NP is NP-complete).
By Behnam Esfahbod, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=3532181

The Final Question: P versus NP

The above image might have confused you, or even you might have earlier heard this question whether the problems belonging in the P set and the NP set are equal. This question is the major unsolved problem in the field of computer science.

TechGeek; Code Lover also Android™ Developer. I am here at Medium to make Computer Science more simpler to the begineers and pros with easy to read blogs.