Categories of Different Computational Problems
Beyond Computation — PART 1
All that you need to know about the Complexity Classes!!
Introduction
During the 1960s, many computer scientists and mathematicians were coming with different decision problems(output can either be “YES” or “NO”). They tried to solve these problems then by utilizing the computational power of computers.
After facing failures in solving some of these problems they started categorizing decision problems into different categories. These categories are decided based on the difficulty level of the problems. And the difficulty level of the problem depends majorly on two factors:-
- The complexity of the problem
- Size of the input provided to an algorithm, which solves that problem
Now let’s directly dive into the main topic!
What are the different Complexity Classes in the field of Computation?
Answering this question straight away would be a bad choice as this field is evolving day by day. But as per the researches done in the field of classical computation up till now, we have categorized complexity classes into 5 sections. They are as follows:-
1. P Problems
P stands for Deterministic Polynomial-time Problems. These problems are relatively easy to solve & easy to verify their solution. Here we can verify every decision generated by solving these problems(i.e. “YES” and “NO” both cases) in polynomial-time.
For example multiplication problem. It is easy to solve & verify. Here, when the input size increases, the time taken to solve this problem grows polynomial times(i.e. O(N^k)). Hence they are called Polynomial-time Problems.
2. NP Problems
NP stands for Non-Deterministic Polynomial-time Problems. These problems are relatively hard to solve but easy to verify their solution. Only the “YES” part of these decision problems can be known here, by verifying the solution.
For example, solving a SUDOKU. It is easy to solve & verify this problem when the grid size is small. But as we increase the grid size, we can observe that the computational power required to solve this problem is very high. Hence it is hard to solve but easy to verify the solution, once it is provided to us.
Herewith the increase in the input size, these problems' complexity grows exponentially (i.e. O(N^N)). Hence they are called Non-Polynomial-time Problems.
3. Co-NP Problems
Co-NP stands for Complemented Non-Deterministic Polynomial-time Problems. They are similar to NP Problems with a slight difference. Firstly, they are hard to solve but easy to verify.
But only the “NO” part of these decision problems can be known, by verifying the solution. Rest everything in these kinds of problems are the same as it was in NP Problems.
4. NP-Hard Problems
NP-Hard stands for Non-Deterministic Polynomial-time Hard Problems. These problems are closest to the most hardest(impossible to solve, according to current research)decision problems discovered up till now.
For example, the Halting Problem. It is one of the most popular problems of the NP-Hard Category. This problem talks about finding that, any program provided with some input value will run forever or not.
5. NPC Problems
NPC stands for Non-Deterministic Polynomial-time Complete Problems. These problems are the subset of NP Problems and are the hardest problems of the NP category. Actually, they are the intersection of NP & NP-Hard problems.
For example, Subset Sum Problem. In this problem, we are given a key & we have to find a subset in the given set which is equal to that key. Now the trivial part of this problem is that the number of elements to be included in the subset is not defined. This makes the problem fall under the NPC category.
Conclusion
So this was all about the categories of different computational problems. We hope now you have a better understanding of how does the computational world in computing works. We will be soon bringing PART-2 of this series — “Beyond Computation”. If you are more curious about this topic then stay tuned with us!!
Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer
