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.
There are more questions alike in the domain of Algorithms since this area is currently under research. There are many stones unturned, but, as far as I know, everything is well-explained here. If you find something incorrect or complicated, let me know in the comments.
Before we get to know the amount of time any algorithm would take, we must grasp the notation used for comparing various algorithms. There are three primary notations used for the asymptotic notation of the algorithms. They are namely Big-Oh, Omega, and Theta notation. So, I recommend you to understand asymptotic notation first and then come here later. Also, let me let you one more thing beforehand that complexity classes are defined using Turing machines, and they are of two types. They are deterministic Turing machines and Non-Deterministic Turing machines.
P, NP, NP-Hard and, NP-Complete are the complexity classes/set for the problems. Any solvable computational problem falls in any one of these categories. Things might look complicated, but they are easier to understand if you grasp them in the following way.
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.
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.
Now, there is something that we must know to understand that why the P set is called a subset of the NP-set. Let us suppose that a deterministic turing machine can solve some problems in a polynomial amount of time. Now, fundamentally, a non-deterministic turing machine can also solve those problems in polynomial time. This fundamental property of a non-deterministic turing machine makes us infer that P is a subset of NP. Mathematically,
P ⊆ NP
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:
1) The problem must belong to the NP-set. Therefore, we can say that the problem must meet all the properties exhibited by the problem belonging in the NP-Set.
2) Every problem belonging to the NP set should be reducible to this problem in a polynomial amount of time.
The following excerpt from Wikipedia can help you understand the reduction in the simplest way:
In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A sufficiently efficient reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.
Intuitively, problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. When this is true, solving A cannot be harder than solving B. “Harder” means having a higher estimate of the required computational resources in a given context (e.g., higher time complexity, greater memory requirement, expensive need for extra hardware processor cores for a parallel solution compared to a single-threaded solution, etc.). The existence of a reduction from A to B can be written in the shorthand notation A ≤m B, usually with a subscript on the ≤ to indicate the type of reduction being used (m : mapping reduction, p : polynomial reduction).
The mathematical structure generated on a set of problems by the reductions of a particular type generally forms a preorder, whose equivalence classes may be used to define degrees of unsolvability and complexity classes.
If you don’t understand the above excerpt, let us assume that a problem is reducible into another. With this assumption, we can say that there is a possible way to convert our problem into that other problem.
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.
The above Euler diagram is for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP. Similarly, the right side of the image is conversely correct 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).
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.
Wikipedia says the following about it- “It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.”
So, you might have understood by now that this question is trivial in such a way that it has remained unanswered since the complexity classes came into existence. So, let us learn that what does it mean if the P set would be equal to the NP set? Let us quickly recap the P and NP classes. In P Class, all the problems could be solved and verified in a polynomial amount of time. Similarly, NP Class problems can be solved in polynomial amounts of time using a non-deterministic turing machine. They take non-polynomial time to solve in a deterministic turing machine. Also, they are verifiable in a polynomial amount of time as well. This question would help us determine whether the problems can be verified and solved in polynomial time or not.
For now, it is a widely used belief that P ≠ NP by 99% of the experts in 2019. If it turns out that this belief is correct then, the P set will be simply a subset of the NP-set, meaning that there are problems in the NP which are harder to compute than to verify. Those Problems that are not present in the P class (but belonging to the NP class) couldn’t be solved in a polynomial amount of time by a deterministic turing machine. But, they would be verifiable in polynomial amounts of time.
If the converse of this belief is true, that is if P = NP. Then, every problem belonging to the NP class would be solvable in a polynomial amount of time using a deterministic turing machine. They are already verifiable in the same amount of time. Whether they can be solved in a polynomial amount of time or not has led us to ask this question whether P=NP or not. But for now, we intuitively believe that P and NP sets are not equal and thereby, assuming that the P is the subset of the NP class.
Most mathematicians and computer scientists expect that P ≠ NP; however, it remains unproven. The official statement of the problem was given by Stephen Cook in 1971 in his seminal paper. You can also read about this open question in more detail at the below Wikipedia link.
From my side, I tried my best to help you learn the most confusing topic, the complexity classes. This topic still might be confusing. But, I hope that this post helped you answer some of your doubts, whether you are a newbie or a pro. Further, we discussed an open question in the field of computer science whether all computational problems are solvable in polynomial complexity or not. If you found something is incorrect or something else, kindly reach me in the comments. Any feedback from you would be appreciated. That is All For Today :)
You can also reach me directly at my LinkedIn handle at here: