In the previous articles, we solved problems of different complexities. Some algorithms have lower rates of growth while others have higher rates of growth. The problems with lower rates of growth are called easy problems (or easy solved problems) and the problems with higher rates of growth are called hard problems (or hard solved problems). This classification is done based on the running time (or memory) that an algorithm takes for solving the problem.
There are lots of problems for which we do not know the solutions. All the problems we have seen so far are the ones that can be solved by computer in deterministic time. Before starting our discussion let us look at the basic terminology we use in this chapter.
Polynomial/Exponential Time
Exponential time means, in essence, trying every possibility (for example, backtracking algorithms) and they are very slow in nature. Polynomial time means having some clever algorithm to solve a problem, and we don’t try every possibility. Mathematically, we can represent these as:
- Polynomial time is O(n k ), for some k.
- Exponential time is O(k n ), for some k.
Also check: max heap deletion algorithm
What is a Decision Problem?
A decision problem is a question with a yes/no answer and the answer depends on the values of input. For example, the problem “Given an array of n numbers, check whether there are any duplicates or not?” is a decision problem. The answer to this problem can be either yes or no depending on the values of the input array.
Also check: spanning tree in data structure
Decision Procedure
For a given decision problem let us assume we have given some algorithm for solving it. The process of solving a given decision problem in the form of an algorithm is called a decision procedure for that problem.
What is a Complexity Class?
In computer science, in order to understand the problems for which solutions are not there, the problems are divided into classes and we call them complexity classes. In complexity theory, a complexity class is a set of problems with related complexity. It is the branch of the theory of computation that studies the resources required during computation to solve a given problem. The most common resources are time (how much time the algorithm takes to solve a problem) and space (how much memory it takes).
Types of Complexity Classes
P Class –
The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time (P stands for polynomial time). P problems are a set of problems whose solutions are easy to find.
NP Class –
The complexity class NP (NP stands for non-deterministic polynomial time) is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. NP class problems refer to a set of problems whose solutions are hard to find, but easy to verify. For better understanding let us consider a college that has 500 students on its roll. Also, assume that there are 100 rooms available for students. A selection of 100 students must be paired together in rooms, but the dean of students has a list of pairings of certain students who cannot room together for some reason. The total possible number of pairings is too large. But the solutions (the list of pairings) provided to the dean, are easy to check for errors. If one of the prohibited pairs is on the list, that’s an error. In this problem, we can see that checking every possibility is very difficult, but the result is easy to validate. That means, if someone gives us a solution to a problem, we can tell them whether it is right or not in polynomial time. Based on the above discussion, for NP class problems if the answer is yes, then there is proof of this fact, which can be verified in polynomial time.
Co-NP Class
Co–NP is the opposite of NP (complement of NP). If the answer to a problem in Co – NP is no, then there is proof of this fact that can be checked in polynomial time.
P – Solvable in polynomial time
NP – Yes answers can be checked in polynomial time
Co – NP – No answers can be checked in polynomial time
So, in this article, we learned about the complexity classes. We will learn more about these in upcoming articles.
Attempt free Data Structures MCQ Test
