NP-complete class
A problem is NP-complete if it is both NP and NP-hard. NP-complete problems are the hard problems in NP.
Features:
- NP-complete problems are special as any problem in NP class can be transformed or reduced into NP-complete problems in polynomial time.
- If one could solve an NP-complete problem in polynomial time, then one could also solve any NP problem in polynomial time.
Some example problems include:
| Complexity Class | Characteristic feature |
| P | Easily solvable in polynomial time. |
| NP | Yes, answers can be checked in polynomial time. |
| Co-NP | No, answers can be checked in polynomial time. |
| NP-hard | All NP-hard problems are not in NP and it takes a long time to check them. |
| NP-complete | A problem that is NP and NP-hard is 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.