Types of Complexity Classes
This article discusses the following complexity classes:
- P Class
- NP Class
- CoNP Class
- NP-hard
- NP-complete
P, NP, CoNP, NP hard and NP complete | Complexity Classes
In computer science, there exist some problems whose solutions are not yet found, the problems are divided into classes known as Complexity Classes. In complexity theory, a Complexity Class is a set of problems with related complexity. These classes help scientists to group problems based on how much time and space they require to solve problems and verify the solutions. It is the branch of the theory of computation that deals with the resources required to solve a problem.
The common resources are time and space, meaning how much time the algorithm takes to solve a problem and the corresponding memory usage.
- The time complexity of an algorithm is used to describe the number of steps required to solve a problem, but it can also be used to describe how long it takes to verify the answer.
- The space complexity of an algorithm describes how much memory is required for the algorithm to operate.
Complexity classes are useful in organising similar types of problems.